1.这道题采用动态规划的思想,用f[i]表示完成前i个任务所需的最小费用,用tim[i]表示前i项任务所需的时间,用mon[i]表示前i项任务一共的费用系数。动归式如下:
f[i]=min{f[j-1]+s*(mon[n]-mon[j-1])+
tim[i]*(mon[i]-mon[j-1])|1<=j<=i};
如果在完成第j项任务是启动一次机器,后面的所有任务完成的时刻都要加上s,所以每启动一次机器的费用为s*(mon[n]-mon[j-1]);
如果把第j项任务和第i项任务和在一起做,则它们的完成时刻为tim[i],所以费用为tim[i]*(mon[i]-mon[j-1])。
得分:100
时间复杂度:O(N^2)
空间复杂度:O(5*N)
#include<iostream> #include<cstdlib> #include<cstdio> using namespace std; int f[5001],g[5001]; int len,wei,n,tim[5001],mon[5001],ti[5001],s; int main(){ scanf("%d%d",&n,&s); for(int b=1;b<=n;++b) { scanf("%d%d",&tim[b],&mon[b]); tim[b]+=tim[b-1]; mon[b]+=mon[b-1]; f[b]=2147483647; } for(int i=1;i<=n;++i) for(int j=1;j<=i;++j) f[i]=min(f[i],f[j-1]+s*(mon[n]-mon[j-1])+tim[i]*(mon[i]-mon[j-1])); printf ("%d",f[n]); return 0; }
2.单调队列优化DP,可以做到On
···
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int f[5001],t[5001],que[5001],dp[5001]; int hd,tl,n,s; int main(){ scanf("%d%d",&n,&s); for(int i=1;i<=n;++i) { scanf("%d%d",&t[i],&f[i]); t[i]+=t[i-1]; f[i]+=f[i-1]; } memset(dp,0x3f,sizeof dp); dp[0]=0;hd=0;tl=0; que[hd]=0; for(int i=1;i<=n;++i) { while(hd<tl&&dp[que[hd+1]]-dp[que[hd]]<=(s+t[i])*(f[que[hd+1]]-f[que[hd]])) hd++; dp[i]=min(dp[i],dp[que[hd]]+(f[i]-f[que[hd]])*t[i]+s*(f[n]-f[que[hd]])); while(hd<tl&&(dp[i]-dp[que[tl]])*(f[que[tl]]-f[que[tl-1]])<=(dp[que[tl]]-dp[que[tl-1]])*(f[i]-f[que[tl]])) tl--; que[++tl]=i; } printf("%d\n",dp[n]); }
···
0.0分
0 人评分
简单的a+b (C语言代码)浏览:489 |
【亲和数】 (C语言代码)浏览:846 |
WU-输入输出格式练习 (C++代码)浏览:1071 |
【魔板】 (C++代码)(时间超限,希望会的帮我改正一下)浏览:730 |
【计算两点间的距离】 (C语言代码)浏览:1473 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:562 |
C语言程序设计教程(第三版)课后习题11.8 (C语言代码)浏览:681 |
字符串的输入输出处理 (C语言代码)浏览:984 |
Pascal三角 (C语言代码)浏览:641 |
字符串比较 (C语言代码)浏览:679 |