1. 题目

2. 题解

额，很水吧。
可是有坑啊。。。
题目中说数据绝对值 $<=104$ 我还真信了。
搞半天下载数据一看发现时 $<=10^4$ 。。。

可是还是WA。。。
看了看发现 memset 搞太大爆 int。。。

思路就是前缀和+环形 dp。。。

~~WY: 求区间和当然用非旋转 treap！~~

首先把环复制一遍，得到一条链。

设 $f1(i,j,k)$ 为把区间 $[i,j]$ 分为 $k$ 份的最大价值。
$f2(i,j,k)$ 为最小价值。
$sum[i,j]$ 为区间 $[i,j]$ 的和

$f1(i,j,k)=max\{f1(i,x,k-1)×(sum[i,j]\ mod\ 10)|i<=x<=j\}$
$f2(i,j,k)=min\{f2(i,x,k-1)×(sum[i,j]\ mod\ 10)|i<=x<=j\}$
$f1(i,j,1)=f2(i,j,1)=sum[i,j]\ mod\ 10$

至于 mod 要为非负数。。。
$a\ mod\ b=a+k\times b\ mod\ b (k\in{Z})$
所以 mod 10 就每次加上一个大于当前数字的可能最小值（且这个数字是 10 的整倍数）再 mod 10。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,arr[105],sum[105],f1[105][105][10],f2[105][105][10],ans1,ans2;
int main()
{
    scanf("%d%d",&n,&m),ans1=INT_MIN,ans2=INT_MAX;
    for(int i=1;i<=(n<<1);i++)
        for(int j=i;j<=(n<<1);j++)
            for(int k=2;k<=m;k++)
                f1[i][j][k]=-1e7,f2[i][j][k]=1e7;
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]),arr[i+n]=arr[i];
    for(int i=1;i<=(n<<1);i++)sum[i]=(sum[i-1]+arr[i]+20000)%10;
    for(int i=1;i<=(n<<1);i++)
        for(int j=0;i+j<=(n<<1);j++)
            f1[i][i+j][1]=f2[i][i+j][1]=(sum[i+j]-sum[i-1]+20000)%10;
    for(int k=2;k<=m;k++)
        for(int l=k;l<=n;l++)
            for(int i=1;(i+l)<=(n<<1);i++)
                for(int j=i;j<(i+l);j++)
                    f1[i][i+l][k]=
                        max(f1[i][i+l][k],f1[i][j][k-1]*((sum[i+l]-sum[j]+100)%10)),
                    f2[i][i+l][k]=
                        min(f2[i][i+l][k],f2[i][j][k-1]*((sum[i+l]-sum[j]+100)%10));
    for(int i=1;i<=n;i++)
        ans1=max(ans1,f1[i][i+n-1][m]),ans2=min(ans2,f2[i][i+n-1][m]);
    printf("%d\n%d\n",ans2,ans1);
    return 0;
}

【题解】数字游戏动态规划 LUOGU – 1043

于2017年5月29日2017年5月29日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复取消回复

【题解】数字游戏 动态规划 LUOGU – 1043

于2017年5月29日2017年5月29日由XZYQvQ发布

1. 题目

2. 题解

XZYQvQ

0 条评论

发表回复 取消回复

【题解】数字游戏动态规划 LUOGU – 1043

发表回复取消回复