欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-06-22 20:27:13
题目链接:https://www.luogu.com.cn/problem/P2734题意:给定一个长度为n(n>=2&&n<=100)的数组a(ai>=1&&ai<=200)。每次可以取一端的数,a和b两个人,a先取,都想要自己总长取最长,问最终两人各取了多少。题解:还是需要自己思考一下的,拿到的时候觉得很难,真的去想却发现远没那么难。这个题我好像之前在那里做到过但是却没多大印象emmm(忘了具体咋做了)。区间dp,枚举长度和起点,l...

题目链接: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

相关标签: 博弈论 DP