首页 > 代码库 > HDU_4570_数位dp
HDU_4570_数位dp
http://acm.hdu.edu.cn/showproblem.php?pid=4570
连题目都看不懂，直接找了题解，copy了过来= =。
一个长度为n的数列，将其分成若干段（每一段的长度要<=20）， 要求∑ai*(2^bi)最小，其中ai是每一段数列的第一项，bi是每一段的长度。比如：n=7，A={1 2 4 4 5 4 3}，将其分成1 2 4| 4 5| 4| 3， 则其所用空间为1*2^3+4*2^2+4*2^1+3*2^1=38， 而如果分成1 2| 4 4 5| 4 3，则其所用空间为1*2^2+4*2^3+4*2^2=52，比38大。
dp[i][j]表示第i项到第j项的最小值。
#include<iostream>#include<cstdio>#include<cstring>#define LL long longusing namespace std;LL a[70],dp[70][70],sum[70];int main(){ int T; scanf("%d",&T); while(T--) { memset(sum,0,sizeof(sum)); int l; scanf("%d",&l); for(int i = 1;i <= l;i++) { scanf("%lld",&a[i]); sum[i] = sum[i-1]+a[i]; } for(int s = 0;s <= l;s++) { for(int i = 1;i <= l && i+s <= l;i++) { int j = i+s; if(s < 20) { dp[i][j] = a[i]; for(int k = i;k <= j;k++) dp[i][j] *= 2; } else dp[i][j] = 2*(sum[j]-sum[i-1]); for(int k = i;k < j;k++) dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]); } } printf("%lld\n",dp[1][l]); } return 0;}
HDU_4570_数位dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。