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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *