零和博弈
有点类似那个Min-Max 游戏
考虑DP【l,r】 为当前考虑到[l,r]当前的先手能得到的最大的分
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int qmi(int a,int b,int mod){int res=1;while(b){if(b&1)res=res*a%mod;b>>=1;a=a*a%mod;}return res;}
int n,q,m;
int a[N];
int dp[110][110];
int s[110][110];
int dfs(int l,int r){
if(l==r)return a[l];
if(~dp[l][r])return dp[l][r];
dp[l][r] = s[l][r] - min(dfs(l+1,r),dfs(l,r-1));
return dp[l][r];
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++)
for(int i=l;i<=r;i++)
s[l][r]+=a[i];
memset(dp,-1,sizeof dp);
int t = dfs(1,n);
int t1 = s[1][n]-t;
cout<<t<<" "<<t1;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _;
//cin>>_;
_ = 1;
while(_--)solve();
return 0;
}
再看这一道很类似的题目~
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int>s(n+10,0);
vector<int>v(n+10,0);
for(int i=1;i<=n;i++)v[i] = stoneValue[i-1];
for(int i=n;i>=1;--i)s[i] = s[i+1]+v[i];
vector<int>dp(n+10,0);
// function<int(int u)>dfs = [&](int u){
// if(u>n)return 0;
// if(u==n)return v[u];
// if(~dp[u])return dp[u];
// dp[u] = s[u] - min({dfs(u+1),dfs(u+2),dfs(u+3)});
// return dp[u];
// };
for(int i=n;i>=1;--i){
dp[i] = s[i]-min({dp[i+1],dp[i+2],dp[i+3]});
// cout<<s[i]<<" "<<dp[i]<<"\n";
}
int t1 = dp[1];
// cout<<t1<<"\n";
int t2 = s[1] - t1;
if(t1>t2)return "Alice";
else if(t1<t2)return "Bob";
return "Tie";
}
};
一开始的DP 是TLE 的改成递推就好了,它是一个单端操作,可以直接改成递推