M_sea

洛谷1430 序列取数
题目描述给定一个长为n的整数序列(n<=1000),由A和B轮流取数(A先取)。每个人可从序列的左端或右端取...
扫描右侧二维码阅读全文
22
2018/08

洛谷1430 序列取数

题目描述

给定一个长为n的整数序列(n<=1000),由A和B轮流取数(A先取)。每个人可从序列的左端或右端取若干个数(至少一个),但不能两端都取。所有数都被取走后,两人分别统计所取数的和作为各自的得分。假设A和B都足够聪明,都使自己得分尽量高,求A的最终得分。

传送门

算法

看上去像个区间DP。

那么设$f[i][j]$表示$i$~$j$这一段区间能取到的最高分。

考虑枚举取到哪里。枚举$k\in [i,j)$,那么可以取$[i,k]$或者$[k+1,j]$。

如果取了左边,那么最高分就是这一段的总分减掉右边的最高分,因为对面必然会把最高分也取掉。
右边同理。

设$sum$为$i$~$j$的和,这个可以前缀和维护。

那么

$$f[i][j]=max_{k=i}^{j-1}(sum,sum-f[k+1][j],sum-f[i][k])$$

最后答案即为$f[1][n]$。

但是这样是$O(n^3)$的,会TLE

考虑优化枚举$k$的循环。我们可以用$L[i][j]$表示$f[i][i],f[i][i+1],f[i][i+2],...,f[i][j]$中的最小值,用$R[i][j]$表示$f[j][j],f[j-1][j],f[j-2][j],...,f[i][j]$中的最小值。

显然$L[i][j]=min(L[i][j-1],f[i][j])$,$R[i][j]=min(R[i+1][j],f[i][j])$。

那么状态转移方程可以优化为

$$f[i][j]=sum-min(0,L[i][j-1],R[i+1][j])$$

注意边界为$f[i][i]=L[i][i]=R[i][i]=a[i]$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int min_(int a,int b) { if (a<b) return a; else return b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}


int a[1010],s[1010];
int f[1010][1010]; //f[i][j]表示i~j先手的最大得分 
int L[1010][1010],R[1010][1010];

int main() {
    int T=read();
    while (T--) {
        int n=read();
        for (re int i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
        for (re int i=1;i<=n;i++) f[i][i]=L[i][i]=R[i][i]=a[i];
        for (re int l=2;l<=n;l++)
            for (re int i=1;i<n;i++) {
                int j=i+l-1; if (j>n) break;
                int sum=s[j]-s[i-1];
                f[i][j]=sum-min_(0,min_(L[i][j-1],R[i+1][j]));
                L[i][j]=min_(L[i][j-1],f[i][j]);
                R[i][j]=min_(R[i+1][j],f[i][j]);
            }
        printf("%d\n",f[1][n]);
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 17 PM

发表评论