挑战2.7.3 Round 1C 2009 C. Bribe the Prisoners 区间dp

题目链接:

https://code.google.com/codejam/contest/189252/dashboard#s=p2

题意:

题解:

区间dp
dp[i][j] 表示释放a[i]~a[j] 【不包含两端的囚犯】所需要的最小费用
枚举其中最先释放的最小费用
则 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]) {i+1<=k<=j-1}

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MS(a) memset(a,0,sizeof(a))
#define MP make_pair
#define PB push_back
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//////////////////////////////////////////////////////////////////////////
const int maxn = 1e5+10;

int P,Q,a[105];
int dp[105][105];

int main(){
    freopen("2.7.3_C-large-practice.in","r",stdin);
    freopen("2.7.3_C-large-practice.out","w",stdout);
    int T = read();
    for(int cas=1; cas<=T; cas++){
        scanf("%d%d",&P,&Q);
        for(int i=1; i<=Q; i++){
            scanf("%d",&a[i]);
        }
        for(int i=0; i<=Q+1; i++)
            for(int j=0; j<=Q+1; j++)
                dp[i][j] = INF;
        a[0] = 0, a[Q+1] = P+1;
        for(int i=0; i<=Q; i++)
            dp[i][i+1] = 0;

        for(int len=2; len<=Q+1; len++){
            for(int i=0; i+len<=Q+1; i++){
                int j = i+len;
                for(int k=i+1; k<j; k++) // 枚举最初释放的囚犯，计算最小费用
                    dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]);
                dp[i][j] += a[j]-a[i]-2; // 这个最小费用还需要加上 与所释放囚犯无关的A[j]-A[i]-2个人的费用
            }
        }

        cout << "Case #" << cas << ": " << dp[0][Q+1] << endl;
    }

    return 0;
}