天津seo网站排名优化公司,网站备案 自己的服务器,大石桥网站制作,宁德市地图也是一道线型动态规划的好题…… 读入每个人的贪婪度之后#xff0c;对其按照从大到小的顺序排序#xff0c;定义状态f[i][j]为前i个人#xff08;排序后#xff09;分j个饼干的答案#xff0c;那么答案为f[n][m],考虑状态转移方程。 1、若给第i个人的饼干数大于1 #x…也是一道线型动态规划的好题…… 读入每个人的贪婪度之后对其按照从大到小的顺序排序定义状态f[i][j]为前i个人排序后分j个饼干的答案那么答案为f[n][m],考虑状态转移方程。 1、若给第i个人的饼干数大于1 那么我们将这i个人的饼干数都减1总共减n他们的怨气值是不会改变的因而这种情况下f[i][j]f[i][j-i]. 2、若给第i个人的饼干数等于1那么我们枚举一个k0≤ki表示从k之后一直到i所有的人的饼干数都是1那么f[i][j]f[k][j-(i-k)]k*∑g[c[p]] (kpi). 我们先预处理出g数组的前缀和即可实现O(n)的转移。 综上我们在两种决策中取最优即可。另外本题要求输出方案我们只需在状态转移时记录每个状态的前驱即可。 1 #include iostream2 #include cstdio3 #include cstring4 #include algorithm5 using namespace std;6 int n,m,f[40][5010],a[40][5010],b[40][5010];7 int s[50],ans[50];8 int g[50],c[50];9 bool cmp(int x,int y) {
10 return g[x]g[y];
11 }
12 void calc(int x,int y) {
13 if(!x) return ;
14 calc(a[x][y],b[x][y]);
15 if(a[x][y]x)
16 for(int i1;ix;i) ans[c[i]];
17 else
18 for(int ia[x][y]1;ix;i) ans[c[i]]1;
19 }
20 int main() {
21 scanf(%d%d,n,m);
22 for(int i1;in;i) {
23 scanf(%d,g[i]);
24 c[i]i;
25 }
26 sort(c1,cn1,cmp);
27 memset(f,0x3f,sizeof(f));
28 f[0][0]0;
29 for(int i1;in;i) s[i]s[i-1]g[c[i]];
30 for(int i1;in;i)
31 for(int ji;jm;j) {
32 f[i][j]f[i][j-i];
33 a[i][j]i;
34 b[i][j]j-i;
35 for(int k0;ki;k)
36 if(f[i][j]f[k][j-(i-k)]k*(s[i]-s[k])) {
37 f[i][j]f[k][j-(i-k)]k*(s[i]-s[k]);
38 a[i][j]k;
39 b[i][j]j-(i-k);
40 }
41 }
42 printf(%d\n,f[n][m]);
43 calc(n,m);
44 for(int i1;in;i) printf(%d ,ans[i]);
45 return 0;
46 } AC Code 转载于:https://www.cnblogs.com/shl-blog/p/10660961.html
