Letter Picking (CF D) (区间DP, 暴力)(0,1,2 Alice 平 bob ,尽可能小,尽可能大)

 思路 :

• 区间dp(区间DP的时间复杂度 不一定是 n^3 ,可能是 n^2 更具题意)
• 直接题 直接 区间dp, 0 Alice 赢 1 平局 2 Bob 赢 (于是 alice 尽可能小, bob 尽可能大)
• alice 选 l , bob 可以选 l+1, 或者 r
• alice 选 r , bob 可选 l 或者 r-1,

看代码就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
string s;
const int N=2e3+5;
int T,n,m,dp[N][N];
inline int make(int op,int p1,int p2){
    if(op!=1)return op;
    return (s[p1]<s[p2]?0:(s[p1]==s[p2]?1:2));
}
int main(){
    T=read();
    while(T--){
        cin>>s;n=s.size();s=" "+s;
        for(int i=1;i<=n;i++)
            for(int j=i;j<=n;j++)dp[i][j]=3;
        for(int len=2;len<=n;len+=2)
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                if(len==2){dp[l][r]=(s[l]==s[r]);continue;}
                int res=2;
                res=min(res,max(make(dp[l+1][r-1],l,r),make(dp[l+2][r],l,l+1)));
                res=min(res,max(make(dp[l+1][r-1],r,l),make(dp[l][r-2],r,r-1)));
                dp[l][r]=res;
            }
        if(dp[1][n]==0)puts("Alice");
        else if(dp[1][n]==1)puts("Draw");
        else puts("Bob");
    }
    return 0;
}

后记:

• 有时候 直接暴力硬做就行了, 不用想性质, 或者说 暴力本身就是一种性质, 在数据范围小的时候,