首页 > 代码库 > 【noi 2.6_6046】数据包的调度机制(区间DP)
【noi 2.6_6046】数据包的调度机制(区间DP)
题意:给定一个队列延迟值为Di的任务,以任意顺序入栈和出栈,第K个出栈的延迟值为(K-1)*Di。问最小的延迟值。
解法:f[i][l]表示完成以第i个任务开始,长度为l,到第i+l-1个任务的最小延迟值。设其中的第j个任务为最后一个出栈的,则f[i][j-i]为先出栈的延迟值,f[j+1][i+l-1-j]+(sum[i+l-1]-sum[j])*(j-i)为接着出栈的延迟值,d[j]*(l-1)为最后一个出栈的延迟值。
因此为:f[i][l]=min(f[i][l],f[i][j-i]+d[j]*(l-1)+f[j+1][i+l-1-j]+(sum[i+l-1]-sum[j])*(j-i));
注意——j是序号,而不是长度,状态不要表示错误。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define N 110 7 #define INF (int)5e5+10 8 9 int f[N][N],d[N],sum[N];10 11 int mmin(int x,int y) {return x<y?x:y;}12 int main()13 {14 int T,n;15 scanf("%d",&T);16 while (T--)17 {18 int i,j,l;19 scanf("%d",&n);20 sum[0]=0;21 for (i=1;i<=n;i++)22 {23 scanf("%d",&d[i]);24 sum[i]=sum[i-1]+d[i];25 }26 /*这里有2种打法27 f[0][0]=0;28 for (l=1;l<=n;l++)29 for (i=1;i+l-1<=n;i++) ......30 */31 for (i=1;i<=n;i++) f[i][1]=0;32 for (l=2;l<=n;l++)33 for (i=1;i+l-1<=n;i++)34 {35 f[i][l]=INF;36 for (j=i;j<=i+l-1&&j<=n;j++)//f[j+1][l-(j-(i-1))]37 f[i][l]=mmin(f[i][l],f[i][j-i]+d[j]*(l-1)+f[j+1][i+l-1-j]+(sum[i+l-1]-sum[j])*(j-i));38 }39 printf("%d\n",f[1][n]);40 }41 return 0;42 }
【noi 2.6_6046】数据包的调度机制(区间DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。