挑战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; }