【CSA49F】【XSY3317】card 博弈论 DP

题目大意

　　不会博弈论的 yww 在和博弈论大师 yxq 玩一个游戏。

　　有 \(n\) 种卡牌，第 \(i\) 种卡牌有 \(b_i\) 张。

　　yww 会先把所有 \(B=\sum_{i=1}^nb_i\) 张卡分成两堆，每堆 \(\frac{B}{2}\) 张。保证 \(B\) 是偶数。

　　他们会轮流从第一堆中取卡牌，每次取一张，yww 先取，直到取完为止。

　　然后他们会轮流从第二堆中取卡牌，每次取一张，yxq 先取，直到取完为止。

　　取完卡牌后，他们会计算自己的得分。假设某人在某一堆中取了 \(x\) 张第 \(i\) 种卡牌，那么就能获得 \(\lfloor\frac{x}{a_i}\rfloor c_i\) 分。

　　每个人的最终得分是这个人在两堆中的得分之和。

　　yxq 想最小化 yww 的得分。

　　作为一名博弈论大师，yxq 每步都会执行最优策略。

　　yww 不会博弈论，所以请你帮 yww 求出他最多能获得多少分。

　　记 \(A=\sum_{i=1}^na_i,B=\sum_{i=1}^nb_i\)；

　　\(1\leq a_i\leq A\leq 2000,1\leq b_i\leq B\leq 500000,2\mid B,1\leq n\leq 2000,1\leq c_i\leq 3000\)；

题解

　　考虑对于一堆牌，yww 先手，他能获得多少分。

　　对于一种牌 \(i\)，如果 \(b_i\equiv -1 \pmod {2a_i}\)，那么先开始拿这种牌的人可以拿到 \(\lfloor \frac{b_i}{2a_i}\rfloor+1\) 张，其他情况都只能拿到 \(\lfloor\frac{b_i}{2a_i}\rfloor\) 张。

　　记 \(b_i\equiv -1 \pmod {2a_i}\) 的牌为特殊的牌，按照 \(c_i\) 从大到小排序，记为 \(d_1,d_2,\ldots,d_k\)，那么最终先手的得分是 \(\sum\limits_i \lfloor\frac{b_i}{2a_i}\rfloor c_i+\sum\limits_{2\nmid i} c_{d_i}\)，后手的得分是 \(\sum\limits_i \lfloor \frac{b_i}{2a_i}\rfloor c_i+\sum\limits_{2\mid i} c_{d_i}\)。

　　这样就可以设计DP状态了：

　　\(f_{i,j,p1,p2}\) 为前 \(i\) 种牌，第一堆分了 \(j\) 张，第一堆有 \(p1\) 种特殊的牌，第二堆有 \(p2\) 种特殊的牌，yww 的最大收益。

　　转移时枚举第 \(i\) 种牌分多少到第一堆。

　　复杂度为 \(O(B^2)\)。

　　注意到收益只与每种牌分到第一堆的牌数 \(\bmod {2a_i}\) 有关，那么DP的时候就可以只枚举 模 \(2a_i\) 的值就好了。

　　还有一个问题，第一堆牌能不能凑出 \(\frac{B}{2}\) 张？

　　对于一种牌，假设我们把 \(k\) 张牌放到了第一堆，那么有 \(\lfloor\frac{b_i-k}{2a_i}\rfloor\) 组 \(2a_i\) 张牌可以随意分配。这个东西等于 \(\lfloor\frac{b_i}{2a_i}\rfloor\) 或 \(\lfloor\frac{b_i}{2a_i}\rfloor -1\)。我们假装它等于 \(\lfloor\frac{b_i}{2a_i}\rfloor -1\)。

　　只可能有 \(O(\sqrt{A})\) 种不同的 \(a_i\)，随便DP一下就好了。

　　记 \(g_{i,j}\) 为用了前 \(i\) 种 \(a_i\) 组出 \(j\) 张卡牌，第 \(i\) 种 \(a_i\) 最少要多少份（每份 \(2a_i\) 张）（\(-1\) 表示组不出）。

　　时间复杂度为 \(O(A^2+B\sqrt A)\)

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
//using namespace std;
using std::min;
using std::max;
using std::swap;
using std::sort;
using std::reverse;
using std::random_shuffle;
using std::lower_bound;
using std::upper_bound;
using std::unique;
using std::vector;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair pii;
typedef std::pair pll;
void open(const char *s){
#ifndef ONLINE_JUDGEchar str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
void open2(const char *s){
#ifdef DEBUGchar str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}
void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}
int upmin(int &a,int b){if(ba){a=b;return 1;}return 0;}
const int N=2010;
const int M=500010;
int f[N][2][2][4*N];
int s[N];
int qs[N];
int c[M];
int g[M];
struct info
{int a,q,v;
};
info a[N];
int cmp(info a,info b)
{return a.v>b.v;
}
int n;
int main()
{open("49F");scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d%d",&a[i].a,&a[i].q,&a[i].v);sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){s[i]=s[i-1]+4*a[i].a;qs[i]=qs[i-1]+a[i].q;}memset(f,0x80,sizeof f);f[0][0][0][0]=0;for(int i=1;i<=n;i++)for(int l1=0;l1<=1;l1++)for(int l2=0;l2<=1;l2++){int x=a[i].q/(2*a[i].a)-1;for(int k=0;k<=a[i].q;k++){int v1=k/(2*a[i].a);int v2=(a[i].q-k)/(2*a[i].a);if(v20)c[a[i].a]+=a[i].q/(2*a[i].a)-1;memset(g,-1,sizeof g);g[0]=0;for(int i=1;i<=s[n];i++)if(c[i]){for(int j=0;j<=qs[n];j++)if(~g[j])g[j]=0;else if(j>=2*i&&(g[j-2*i]>=0&&g[j-2*i]

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！