google code jam 2009 round1 c

リンク:https://code.google.com/codejam/contest/189252/dashboard#s=p2犯人を釈放するには、身の回りの犯人に金貨を一つずつ渡して、空き家や壁まで広げなければならない.釈放が必要な犯人の番号をいくつかあげて、どのような順番で釈放すれば金貨の数を最小限に抑えることができるかを聞きました.分析:问题を分解することができて、1つの必要な金货を釈放するのは1)この人を釈放する必要があって、2)左のすべての犯人を釈放する必要があって、3)右の犯人を釈放する必要があります.この3つの部分の合計.左と右もこのように分解することができ、最後に問題全体が最初に釈放された囚人を列挙することになる.各大区間には小さい区間の必要金貨数が必要であるため,dpを用いて1区間内のすべての犯人を釈放するために必要な金貨の総数を求める.定義a[i]はi番目の犯人の自分の番号を表し、またa[0]=0である.a[q+1] = p+1. 定義dp[i][j]は、i番目からj番目の犯人までの間のすべての犯人を釈放するために必要な金貨数(i,jの2人の犯人を除く)を示すように定義された後の最後の答えがdp[0][q+1]である.小さい区間長i=2−>q+1から列挙を開始し、同一区間長において各可能区間起点jを列挙し、最初に釈放された犯人番号がkの場合、dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i])であるため、各可能kを列挙する必要がある.最後に、最初の釈放に必要な金貨を加える必要があります.dp[j][j+i] += dp[j][j+i]+a[j+i]-a[i]-2.

/* GCJ 2009 round1 C 2015 07 31 */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1009
#define INF 0x3f3f3f3f
int a[M];
int dp[M][M];
int main()
{
    freopen("C-large-practice.in","r",stdin);
    freopen("out1.txt","a+",stdout);
    int t;
    scanf("%d",&t);
    int kase = 1;
    while(k <= t)
    {
        int p,q;
        scanf("%d %d",&p,&q);
        for(int i = 1;i <= q;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+q+1);
        a[0] = 0;
        a[q+1] = p+1;
        for(int i = 0;i <= q;i++)
            dp[i][i+1] = 0;
        for(int i = 2;i <= q+1;i++)//      2     
        {
            for(int j = 0;j+i <= q+1;j++)
            {
                int temp = INF;
                int k;
                for(k = j+1;k < j+i;k++)  //       ，         。
                {  //        ，   j+1    
                    temp = min(temp,dp[j][k]+dp[k][j+i]);
                }
                //  k          。
                dp[j][k] = temp+a[k]-a[j]-2; //                
            }
        }
        printf("Case #%d: %d
",kase++,dp[0][q+1]);
    }
    return 0;
}