hdu6199 gems gems gems（轮流取石子使差最大/小）

201709

• 一开始感觉k要取到200,但是内存爆了。
• 然后跑一下程序（下文代码中35行），发现K取160就行了。
• 注意：dfs内存会爆。

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
#define de(a) cout<<#a<<" = "<<a<<endl
#define dd(a) cout<<#a<<" = "<<a<<" "
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//-----
const int N=20001;
const int M=160;
int n;
int sum[N],f[N][M][2];
int main(){
    int T;scanf("%d",&T);
    while(T--) {
        ///
        scanf("%d",&n);
        ///init
        memset(f,0,sizeof(f));
        ///read
        rep(i,1,n+1) scanf("%d",&sum[n+1-i]);
        ///get sum
        rep(i,1,n+1) sum[i]=sum[i]+sum[i-1];
        ///solve
        rep(i,0,n+1) {
            for(int k=0;(1+k)*k/2<=(n-i)+2&&i>=k;++k) {
                if(k>=M) {de(i);de(k);}
                rep(x,0,2) {
                    int r1=f[i-k][k][1-x];
                    int t1=sum[i]-sum[i-k];
                    int res=0;
                    if(x) {
                        res=r1-t1;
                    } else {
                        res=r1+t1;
                    }
                    if(i>=k+1) {
                        int r2=f[i-(k+1)][k+1][1-x];
                        int t2=sum[i]-sum[i-(k+1)];
                        if(x) {
                            res=min(res,r2-t2);
                        } else {
                            res=max(res,r2+t2);
                        }
                    }
                    f[i][k][x]=res;
                }
            }
        }
        ///print
        printf("%d\n",f[n][1][0]);
    }
    return 0;
}