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\×b\ mod\ b (k\in{Z})$
所以 mod 10就每次加上一个大于当前数字的可能最小值(且这个数字是10的整倍数)再 mod 10。

代码: