USACO Training3.3 A Game【区间Dp】 By cellur925
2024-08-30 16:37:34
一股浓浓的博弈论香气...然而本蒟并不会博弈论。
开始用双端队列+假的dp水过了24pts水数据。
其实是布星的,两人都绝顶聪明会深谋远虑不像我只看眼前,所以上述算法错误。
正解:区间dp。决策有两种:从右边取或是左边。而且答案是由小部分一步步推到大部分的,所以区间dp再适合不过啦。
状态:如常。$f[i][j]$表示拿从i到j玩家1得到的最大得分。
转移方程:$f[i][j]=max(sub[j]-sub[i-1]-f[i][j-1],sub[j]-sub[i-1]-f[i+1][j])$ sub[]是前缀和数组。
第一个:当1拿了最右,则2拿i到j-1,剩下的归1;第二个同理。
目标:$f[1][n]$ (玩家1) $sub[n]-f[1][n]$(玩家2)
Code
#include<cstdio>
#include<algorithm> using namespace std; int n;
int a[],sub[];
int f[][]; int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]),sub[i]=sub[i-]+a[i],f[i][i]=a[i];
for(int i=n-;i>=;i--)
for(int j=i+;j<=n;j++)
f[i][j]=max(sub[j]-sub[i-]-f[i+][j],sub[j]-sub[i-]-f[i][j-]);
printf("%d %d",f[][n],sub[n]-f[][n]);
return ;
}
这么水都不会,我好菜呀。。。
Update:倒序循环的原因 $f[i][j]$需要从$f[i+1][j]$转移过来...
最新文章
- 如何设置UILabel中的字体的间距
- python字典
- 通过CSS使文本框中输入的小写字母变大写字母
- linux常见命令的列表
- 模拟键盘输入 : SendMessage, keybd_event, PostKeybdMessage
- Android(java)学习笔记204:自定义SmartImageView(继承自ImageView,扩展功能为自动获取网络路径图片)
- angular.js学习
- CopyOnWriteArrayList源代码阅读器
- Tiny6410之按键裸机驱动
- WampServer 下载以及安装问题
- 关于MAC设置免费的动态壁纸
- c++中sort()函数的用法
- Python笔记 #21# DHNN
- 17秋 软件工程 团队第三次作业 预则立&;他山之石
- 一天掌握python爬虫
- Gluster vs Ceph:开源存储领域的正面较量
- Kali2.0可用国内源更新sources.list
- CopyOnWriteArrayList分析
- druid
- Spring Boot 中修改端口和上下文路径