Wuyanru's blog
0%

[CF1939D] Big Persimmon

发表于 分类于 ，

肥肠神秘的 dp。

教练看别人代码给我们讲会了这题（

题目链接。

题意

现在有 块水果排成一个序列，第 块大小是 。

Alice 和 Bob 两个人现在要来吃水果，吃掉大小为 的水果需要 秒。

当一个人吃完手里的水果时，可以从当前序列最左端或最右端拿起一块继续吃。

两个人同时需要选择时，Alice 先选。

两个人都采用最优策略，问两个人最终吃的水果大小之和各是多少。

。

。

。

题解

首先，因为 Alice 和 Bob 每个人每次都是从序列两端取水果，所以当前剩下的水果序列一定是原序列的一段区间 。

考虑进行区间 dp，设 表示当前还有 里的水果没有被吃，现在该 Alice/Bob 选水果了，另一个人吃完这一块水果还要 秒，此时这个人最多能吃到多少水果。

显然，整个问题的答案是 。

容易发现，我们的复杂度是 的，显然过不去。精细实现可以拿到 分。

考虑对于一个区间 ， 的上界是多少。

显然当 时有上界 。

容易发现，如果有 ，那么这个上界就是 。

那么这个时候合法的 状态数就是 ，这个时候我们的总复杂度就是 的。

可以拿到 分。

考虑只保留 的状态，那么状态总数就只有 ，问题主要在于如何转移。

首先发现，若此时直接枚举当前这个人选走了哪部分，使得另一个人手里的被吃完了，那么此时的 一定是合法的。

但这样转移是 的，总时间复杂度仍然是 。

又可以发现，若一个状态 有 ，若此时再从左边拿一个，由于 ，则这个状态仍然合法。

这样，我们可以 直接转移从左边拿一个的方案数。

那么这个时候就只需要考虑右边怎么拿了。

为了转移的状态合法，我们直接强制钦定右边一次性拿到两人反转，复杂度仍为 。

这样，我们就将整道题的复杂度降为了 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int dp[44000001][2];
int id[2001][2001];
int pre[2001];
int num[2001];
int wh[20001];
int a[2001];
int n,cnt;
#define dp(l,r,x,p) dp[id[l][r]+x][p]
int main()
{
    n=read(),num[n]=n;
    for(int i=1;i<=n;i++)
    {
        pre[i]=pre[i-1]+(a[i]=read());
        wh[pre[i]]=i;
    }
    for(int i=1;i<=pre[n];i++) if(!wh[i]) wh[i]=wh[i-1];
    for(int i=1;i<n;i++)
    {
        int val=0,j=i;
        while(j>1&&val<a[i+1]) j--,val+=a[j];
        num[i]=j;
    }
    for(int l=1;l<=n;l++) for(int r=l;r<=n;r++)
    {
        id[l][r]=cnt;
        int val=r==n?a[l-1]:a[r+1];
        cnt+=val+1;
    }
    for(int i=1;i<=n;i++)
    {
        int lim=i==n?a[i-1]:a[i+1];
        for(int j=0;j<=lim;j++) dp(i,i,j,0)=a[i];
        for(int j=1;j<=lim;j++) dp(i,i,j,1)=a[i];
    }
    for(int len=2;len<=n;len++) for(int l=1,r=len;r<=n;l++,r++)
    {
        int lim=r==n?a[l-1]:a[r+1],sum=pre[r]-pre[l-1];
        for(int x=1;x<=lim;x++) for(int w=0;w<2;w++)
        {
            if(sum<=x)
            {
                dp(l,r,x,w)=sum;
                continue;
            }
            if(a[l]<x) dp(l,r,x,w)=a[l]+dp(l+1,r,x-a[l],w);
            else dp(l,r,x,w)=sum-dp(l+1,r,a[l]-x,1-w);
            int f=wh[max(0,pre[r]-x)]+1,e=pre[r]-pre[f-1];
            if(e<x) dp(l,r,x,w)=max(dp(l,r,x,w),e+dp(l,f-1,x-e,w));
            else dp(l,r,x,w)=max(dp(l,r,x,w),sum-dp(l,f-1,e-x,1-w));
        }
        dp(l,r,0,1)=min(dp(l,r-1,a[r],1),dp(l+1,r,a[l],1));
        dp(l,r,0,0)=sum-dp(l,r,0,1);
    }
    printf("%d %d\n",dp(1,n,0,0),dp(1,n,0,1));
    return 0;
}

感谢观看！