Description
CZL发明了一种叫作舳舻牌的双人纸牌游戏，据说具有提神醒脑，延年益寿的功效。这次，CZL和他的对手YYY进行游戏，CZL先手。
首先，桌子上平铺着N张牌，从1至N标号。每张牌都有一个收益值，可正可负，收益值用Wi表示。每张牌对每个人都有一个诱惑值，与收益值无关。
游戏开始时，CZL先手，两人交替进行游戏。轮到某个人时，ta报出一个整数X，然后拿走桌上剩余的牌中所有诱惑值小于等于X的牌（至少拿一张）。当桌上没有牌时，游戏结束。收益值总和高者获胜。
我们对CZL和YYY的智商还是不怀疑的，所以可以保证他们都是按照最优策略操作，使自己的分数尽量多。请你编程求出CZL最终的收益值之和。
Solution
哇，一看就像是一个博弈题
但是做不了TAT
那用什么做？
发现牌数很少，那么诱惑值的种类也很少。
那么只用枚举两人分别的诱惑值就可以了。
DP！
用DP怎么做
发现在牌数为0时的收益值肯定不能直接去求。
那么就倒着做。
维护一个f[i,j]表示在CZL操作后取了诱惑值i及以上的牌，YYY取了诱惑值为j及其以上的牌，然后使得CZL的收益数最大。
维护一个g[i,j]表示在YYY操作后取了诱惑值j及以上的牌，CZL取了诱惑值为j及其以上的牌，然后使得YYY的收益数最大。
然后有两个辅助数组cnt[i,j]表示对CZL来说诱惑值i及其以上，对YYY来说诱惑值在的牌数在j及其以上的牌数。s[i,j]表示对CZL来说诱惑值i及其以上，对YYY来说诱惑值在的牌数在j及其以上的牌数的收益值和。这两个数组都可以用后缀和搞定。
因为是博弈，假设f[i,j]是从g[i,k]转移过来的，那么肯定要要求f[i,j]=max(f[i,j],s[i,j]-g[k,j])就是现在CZL要取i及以上的诱惑值，注意转移必须要在cnt[i,j]>cnt[k,j]的时候再能转移，否则f[i,j]=f[k,j]。g[i,j]类似。
这样做不加优化只有30分
优化
因为发现转移中有一个max，那么肯定可以打线段树维护了。
但是还有更好的方法。
因为发现s[i,j]是不变的，那么把s[i,j]提取出来。那么f[i,j]=max(f[i,j],s[i,j]-g[k,j])=s[i,j]-min(g[k,j])，那么设一个e[j]=min(g[k,j])就好了。g[i,j]类似。
Code
#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
const int maxn=1007;
typedef long long ll;
typedef int arr[maxn];
using namespace std;
ll i,j,k,l,t,n,m,ans,yi,er;
int a[maxn],b[maxn],c[maxn];
ll e[maxn],f[maxn][maxn],g[maxn][maxn],d[maxn];
int cnt[maxn][maxn];
ll s[maxn][maxn];
void lisan(int *x){
arr data;
fo(i,1,n)data[i]=x[i];
sort(data+1,data+1+n);
int o=unique(data+1,data+1+n)-data-1;
fo(i,1,n)x[i]=lower_bound(data+1,data+1+n,x[i])-data;
}
int main(){
//freopen("poker.in","r",stdin);
//freopen("poker.out","w",stdout);
scanf("%d",&n);
fo(i,1,n){
scanf("%lld",&c[i]);
}
fo(i,1,n){
scanf("%lld%lld",&a[i],&b[i]);
}
lisan(a);lisan(b);
yi=a[n];er=b[n];
fod(i,n,1){
s[a[i]][b[i]]+=c[i];
cnt[a[i]][b[i]]+=1;
}
fod(i,n,1){
fod(j,n,1){
s[i][j]=s[i][j]+s[i+1][j]+s[i][j+1]-s[i+1][j+1];
cnt[i][j]=cnt[i][j]+cnt[i+1][j]+cnt[i][j+1]-cnt[i+1][j+1];
}
}
fod(i,n,1){
fod(j,n,1){
if(cnt[i][j]==cnt[i+1][j])f[i][j]=f[i+1][j];
else{
f[i][j]=s[i][j]-d[j];
}
if(cnt[i][j]==cnt[i][j+1])g[i][j]=g[i][j+1];
else{
g[i][j]=s[i][j]-e[i];
}
e[i]=min(e[i],f[i][j]);
d[j]=min(d[j],g[i][j]);
}
}
printf("%lld\n",f[1][1]);
}