POJ 1678 I Love this Game!#dp博弈
2024-08-24 18:35:34
http://poj.org/problem?id=1678
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int INF=10e8;
int n,a,b,p[10005],dp[10005]; int dfs(int x)
{
if(dp[x]!=-INF)
return dp[x]; int ans=INF;
for(int i=x+1;i<n;i++)
if(p[i]-p[x]>=a&&p[i]-p[x]<=b)//对方要尽量取差值大的,那么要得到差值尽可能小的
ans=min(ans,p[x]-dfs(i)); //== ans=max(ans,dfs(i)); ans=p[x]-ans;
if(ans==INF)
return dp[x]=p[x];
return dp[x]=ans;
} int op()
{
int ans=-INF;
for(int i=0;i<n;i++)
if(p[i]>=a&&p[i]<=b)
ans=max(ans,dfs(i));
return ans==-INF?0:ans;
} int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&a,&b);
for(int i=0;i<n;i++)
{
scanf("%d",&p[i]);
dp[i]=-INF;
}
sort(p,p+n);
printf("%d\n",op());
}
return 0;
}
最新文章
- EasyUI中datagrid控件的使用 设置多行表头(两行或多行)
- java mail发送邮件
- typeid详解
- Javascript中setTimeout()的用法详解
- 著名的安装制作软件InnoSetup的源码及示例源码-The installation of a well-known software s source code and sample InnoSetup source
- hdu 1689 Just a Hook
- js原生代码编写一个鼠标在页面移动坐标的检测功能,兼容各大浏览器
- logfile提示stale错误解决方法
- HTML5基础篇章1
- Java8-如何构建一个Stream
- jqgrid postData post方式累加参数,缓存了原来的数据
- HDU3567
- input text 去掉标签下拉提示
- ***php进行支付宝开发中return_url和notify_url的区别分析
- Android - Resource 之 Menu 小结
- Hadoop权威指南
- NumPy 切片和索引
- BZOJ 1208 宠物收养所 set+二分
- ios获取文件的MD5值
- STL Set和multiset 容器