【CH5105】Cookies

  • Z时代
  • 2024-01-10
  • 分类：综合

coding

也是一道线型动态规划的好题……

读入每个人的贪婪度之后，对其按照从大到小的顺序排序，定义状态f[i][j]为前i个人（排序后）分j个饼干的答案，那么答案为f[n][m],考虑状态转移方程。

1、若给第i个人的饼干数大于1 ，那么我们将这i个人的饼干数都减1（总共减n），他们的怨气值是不会改变的，因而这种情况下，f[i][j]=f[i][j-i].

2、若给第i个人的饼干数等于1，那么我们枚举一个k（0≤k<i），表示从k之后一直到i所有的人的饼干数都是1，那么f[i][j]=f[k][j-(i-k)]+k*∑g[c[p]]    (k<p<=i).

我们先预处理出g数组的前缀和，即可实现O(n)的转移。

综上，我们在两种决策中取最优即可。另外，本题要求输出方案，我们只需在状态转移时记录每个状态的前驱即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5usingnamespace std;
 6int n,m,f[40][5010],a[40][5010],b[40][5010];
 7int s[50],ans[50];
 8int g[50],c[50];
 9bool cmp(int x,int y) {
10return g[x]>g[y];
11}
12void calc(int x,int y) {
13if(!x) return ;
14    calc(a[x][y],b[x][y]);
15if(a[x][y]==x) 
16for(int i=1;i<=x;i++) ans[c[i]]++;
17else
18for(int i=a[x][y]+1;i<=x;i++) ans[c[i]]=1;
19}
20int main() {
21     scanf("%d%d",&n,&m);
22for(int i=1;i<=n;i++)  {
23         scanf("%d",&g[i]);
24         c[i]=i;
25    }
26     sort(c+1,c+n+1,cmp);
27     memset(f,0x3f,sizeof(f));
28     f[0][0]=0;
29for(int i=1;i<=n;i++) s[i]=s[i-1]+g[c[i]];
30for(int i=1;i<=n;i++)
31for(int j=i;j<=m;j++) {
32             f[i][j]=f[i][j-i];
33             a[i][j]=i;
34             b[i][j]=j-i;
35for(int k=0;k<i;k++)
36if(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);
44for(int i=1;i<=n;i++) printf("%d ",ans[i]);
45return0;
46 }

AC Code

以上是 【CH5105】Cookies 的全部内容， 来源链接： utcz.com/z/509483.html

回到顶部