$CH5105\ Cookies$ 线性$DP+$贪心
2024-09-01 11:15:58
是很有趣的一道题 : )
Sol
第一反应就是f[i][j]表示前i个小朋友分j块饼干的最小怨气值
但是一个孩子所产生的怨气值并不固定,它与其他孩子获得饼干的情况有关
这里可以用到一个贪心,就是贪婪度大的孩子应该获得尽量多的饼干
所以先按照贪婪度由大到小排序,那么获得的饼干数也会是非严格单调递减的
然而发现很还是难转移,因为这样直接转移需要前一个孩子获得的饼干数与比前一个孩子获得饼干多的孩子数
在现有的DP状态下,很难高效维护这两种信息
对状态做一个等价转化:
1.若第i个孩子获得的饼干数大于1
可以将所有的孩子获得的饼干同时减去1,它们的相对值并没有改变,所以这样所得到的答案任然是正确的
$f[i][j]=f[i][j-i]$
2.若第i个孩子获得的饼干数等于1
就要枚举k(1<=k<=i)表示在i前获得饼干数为1的第一个孩子是谁
$f[i][j]=min(f[k][j-(i-k+1)+(k-1)*\sum_{t=k}^{i}g[t])$
最后,这题还要记录答案。
在DP中需要给出方案时,一般的做法是额外使用一些与DP状态大小相同的数组记录下来每个状态的最优解是从何处转移而来的.最终,在DP求出最优解后,通过一次递归,沿着记录的每一步回到初态,即可得到一条从初态到最优解的转移路径,也就是所求的具体方案.
这题的答案统计与一般的题目不太一样,要细心.
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define Rg register
#define il inline
#define db double
#define ll long long
#define inf 2100000000
#define go(i,a,b) for(Rg int i=a;i<=b;++i)
#define yes(i,a,b) for(Rg int i=a;i>=b;--i)
using namespace std;
il int read()
{
int x=,y=;char c=getchar();
while(c<''||c>''){if(c=='-')y=-;c=getchar();}
while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}
return x*y;
}
struct node{int dat,pos;}g[];
struct node1{int i,j;}a[][];
il bool cmp(node x,node y){return x.dat>y.dat;}
int n,m,ans[],f[][];
int main()
{
n=read(),m=read();
go(i,,n)go(j,,m)f[i][j]=inf;f[][]=;
go(i,,n)g[i].dat=read(),g[i].pos=i;
sort(g+,g+n+,cmp);
go(i,,n)g[i].dat+=g[i-].dat;
go(i,,n)
go(j,i,m)
{
f[i][j]=f[i][j-i];a[i][j]=(node1){i,j-i};
go(k,,i)
if(f[i][j]>f[k-][j-(i-k+)]+(k-)*(g[i].dat-g[k-].dat))
f[i][j]=f[k-][j-(i-k+)]+(k-)*(g[i].dat-g[k-].dat),a[i][j]=(node1){k-,j-(i-k+)};
}
int t1=n,t2=m;
while(t1)
{
if(t1==a[t1][t2].i){go(i,,t1)ans[g[i].pos]++;}
else{go(i,a[t1][t2].i+,t1)ans[g[i].pos]++;}
int tt=t1;t1=a[t1][t2].i;t2=a[tt][t2].j;
}
printf("%d\n",f[n][m]);
go(i,,n)printf("%d ",ans[i]);
return ;
}
最新文章
- GCC for Win32开发环境介绍
- Windows Azure Service Bus (3) 队列(Queue) 使用VS2013开发Service Bus Queue
- Delphi XE5 android 获取网络状态
- nodejs初探(二)第一个nodejs程序“hello world”
- [转]C# 应用程序安装部署步骤,安装前操作,先退出程序后卸载。
- BZOJ 1968 约数研究
- 第六十二篇、AFN3.0封装网络请求框架,支持缓存
- html笔记 横向两列布局
- Nginx对于图片,js等静态文件的缓存设置
- HDU 1242 rescue and 优先级队列的条目
- 批量升级BMC固件asu64、ipmitool
- 堆/栈的比较 以及 malloc/new动态内存的开辟
- SharePoint 2013 代码实现自定义的站点模版创建Site Collection
- iframe自适应高度问题
- Sublime Text学习笔记
- PHP 分支与循环
- [转载] 基于Redis实现分布式消息队列
- Windows Server 2012开启多人远程
- 网络基础Cisco路由交换二
- 1.3 java与C++有什么异同
热门文章
- composer基本使用
- 13 -1 BOM和定时器
- 你真的知道你看到的UTF-8字符是什么吗?
- Logtail提升采集性能
- oracle使用TKPROF 工具来查询SQL性能状态
- React事件用法
- 自然语言处理课程(二):Jieba分词的原理及实例操作
- 洛谷P3313 [SDOI2014]旅行 题解 树链剖分+线段树动态开点
- html设置<;input type=";text";>;内的内容自动为大写
- Python--day38--JoinableQueue解决生产者消费者模型