首页 > 代码库 > HDU 4283：You Are the One（区间DP）
HDU 4283：You Are the One（区间DP）
http://acm.hdu.edu.cn/showproblem.php?pid=4283
题意：有n个数字，不操作的情况下从左到右按顺序输出，但是可以先让前面的数字进栈，让后面的数字输出，然后栈里的数字再输出。执行完各种操作后，第i个数字输出的代价是w[i] * （i-1）。问如何弄才能使得代价最小，输出。
思路：做了半个下午。好菜啊QAQ。
考虑两种情况：
1、左区间的元素先输出，然后右区间的元素再输出。这个时候方程为 dp[i][j] = dp[i][k] + dp[k+1][j] + sum(k+1,j) * (i-k+1)。
2、左区间的元素进栈，右区间的元素先输出，然后左区间元素倒序输出（因为进了栈顺序反了）。方程为 dp[i][j] = dp[k+1][j] + sum(i,k) * (j-k) + tmp.（tmp是倒序输出的代价）
然后对于这两种情况取优就好了。
都是细节没搞清楚才做好久。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 #define N 105 6 typedef long long LL; 7 LL dp[N][N], w[N], pre[N]; 8 9 int main() {10 int t, cas = 0;11 scanf("%d", &t);12 while(t--) {13 // char s[2];14 // if(cas == 0) scanf("%s", s);15 int n; scanf("%d", &n);16 memset(dp, 0x3f3f3f3f, sizeof(dp));17 for(int i = 1; i <= n; i++) scanf("%lld", &w[i]), dp[i][i] = 0;18 for(int i = 1; i <= n; i++) pre[i] = pre[i-1] + w[i];19 for(int len = 1; len < n; len++) {20 for(int i = 1; i + len <= n; i++) {21 int j = i + len;22 for(int k = i; k < j; k++) {23 // a的情况是前后的区间都不入栈24 LL a = dp[i][k] + dp[k+1][j] + (pre[j] - pre[k]) * (k + 1 - i);25 LL tmp = 0;26 for(int cnt = k; cnt >= i; cnt--) tmp += w[cnt] * (k - i);27 // tmp 求倒着出栈的代价28 // b的情况是前面的入栈,让后面的区间直接出来29 LL b = dp[k+1][j] + (pre[k] - pre[i-1]) * (j - k) + tmp;30 dp[i][j] = min(dp[i][j], min(a, b));31 }32 }33 }34 printf("Case #%d: %lld\n", ++cas, dp[1][n]);35 }36 return 0;37 }
HDU 4283：You Are the One（区间DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。