【题目描述】
将一圈整数分为m个部分, 使得每个部分的和对10取模后乘积最大
思路:
化环为链+区间dp
设d(l,r,k)是将区间[l,r]分为k段的最优解
那么就有d(l,r,k)=d(l,c,s)*d(c+1,r,k-s)(l<=c\<r, 1<=s\<k)
答案为max/min{d(i,i+n-1,m)}(1<=i<=n)
代码:
1 |
|
将一圈整数分为m个部分, 使得每个部分的和对10取模后乘积最大
化环为链+区间dp
设d(l,r,k)是将区间[l,r]分为k段的最优解
那么就有d(l,r,k)=d(l,c,s)*d(c+1,r,k-s)(l<=c\<r, 1<=s\<k)
答案为max/min{d(i,i+n-1,m)}(1<=i<=n)
1 | #include <iostream> |