luogu P2734 [USACO3.3]游戏 A Game(博弈，区间dp)

题目链接：https://www.luogu.com.cn/problem/P2734

题意：给定一个长度为n(n>=2&&n<=100)的数组a（ai>=1&&ai<=200）。每次可以取一端的数，a和b两个人，a先取，都想要自己总长取最长，问最终两人各取了多少。

题解：还是需要自己思考一下的，拿到的时候觉得很难，真的去想却发现远没那么难。

这个题我好像之前在那里做到过但是却没多大印象emmm（忘了具体咋做了）。

区间dp，枚举长度和起点，len=1是dpij=ai，len=2时dpij=max(ai,aj)//(j=i+len-1)。len>2时两种方案先取左边/先取右边。

dp[i][j]表示在i-j区间内，先取的人能取到的最大值。再状态转移就ok了。

******我感觉我有做dp题的天赋emmmm。冲！！今天博弈过两天dp。

代码：

#include <bits/stdc++.h>

#define ll long long
#define pi acos(-1)
#define pb push_back
#define mst(a, i) memset(a, i, sizeof(a))
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define dbg(x) cout << #x << "===" << x << endl
using namespace std;
template <class T> void read(T &x) {
    T res = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        res = (res << 3) + (res << 1) + c - '0';
        c = getchar();
    }
    x = res * f;
}
void print(ll x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
const ll maxn = 1e2 + 10;
const ll mod = 1e9 + 7;

ll n, a[maxn], dp[maxn][maxn], sum[maxn];
// ll gcd(ll a,ll b){return (b==0)?a:gcd(b,a%b);}
// ll qpow(ll a,ll p,ll mod){ll
// ans=1;a=a%mod;while(p){if(p&1)ans=(ans*a)%mod;p>>=1;a=(a*a)%mod;}return ans;}
int main() {
    ll _s = 1;
    // read(_s);
    // for(ll i=100;i<=150;i++) printf("a[%lld]=%lld\n",i,a[i]);
    for (ll _ = 1; _ <= _s; _++) {
        read(n);
        for (ll i = 1; i <= n; i++) {
            read(a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        // for(ll i=1;i<=n;i++) cout<<sum[i]<<" ";cout<<endl;
        for (ll len = 1; len <= n; len++) {
            for (ll i = 1; i+len-1 <= n; i++) {
                ll t=i+len-1;
                if (len == 1) dp[i][t] = a[i];
                if (len == 2) dp[i][t] = max(a[i], a[t]);
                if (len > 2) {
                    dp[i][t] =
                        max(a[i] + sum[t] - sum[i] - dp[i + 1][t],
                            sum[t - 1] - sum[i - 1] - dp[i][t - 1] + a[t]);
                }
            }
        } /*
         for(ll i=1;i<=n;i++){
             for(ll j=1;j<=n;j++){
                 cout<<dp[i][j]<<" ";
             }
             cout<<endl;
         }*/
        cout << dp[1][n] << " " << sum[n] - dp[1][n] << endl;
    }
    return 0;
}
/*
input:::

output:::

*/

 

本文地址：https://blog.csdn.net/I_have_a_world/article/details/109274989