首页 > 代码库 > LightOJ 1422 (区间DP)
LightOJ 1422 (区间DP)
题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27130
题目大意：按顺序去参加舞会。每个舞会对衣服都有要求。可以连续穿好多件衣服。需要时候就脱下来，但是一旦脱下来，这件衣服就报废了。问最少需要几件衣服。
解题思路：
很难想出这题是个区间DP。
DP边界：
dp[i][i]=1。也就是说每个舞会换件衣服。当然这个不是最优的。
对于dp[i][j]:
如果cos[i]=cos[j]，dp[i][j]=dp[i][j-1]，很明显i的衣服穿在最底，在j的时候就能拿出来再用了。这是第一步优化。
之后枚举中间点k，注意(i<=k<j)，
如果cos[i]=cos[k]，那么k的衣服就是i的衣服了。那么dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j])
注意这里是dp[i][k]，而不是dp[i][k-1]。
#include "cstdio"#include "cstring"#include "iostream"using namespace std;#define maxn 105#define inf 0x3f3f3f3fint cos[105],dp[105][105];int main(){ //freopen("in.txt","r",stdin); int T,n,no=0; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&cos[i]); for(int i=1;i<=n;i++) dp[i][i]=1; for(int p=1;p<=n;p++) { for(int i=1;i<=n;i++) { int j=i+p; dp[i][j]=inf; if(cos[i]==cos[j]) dp[i][j]=dp[i][j-1]; for(int k=i;k<j;k++) if(cos[i]==cos[k]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]); } } printf("Case %d: %d\n",++no,dp[1][n]); memset(dp,0,sizeof(dp)); }}
LightOJ 1422 (区间DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。