(luogu1043) 数字游戏

发表于 分类于 ，

一个新的 dp 模版

【题目描述】

将一圈整数分为 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;
const int Mn(115);
const int Mm(15);
int s[Mn];
long long dmn[Mn][Mn][Mm],dmx[Mn][Mn][Mm];
long long fmn(int l,int r,int k) //最大值
{
    if(dmn[l][r][k]!=-1)	return dmn[l][r][k];
    else
    {
        if(k==1)
        {
            int ans((s[r]-s[l-1])%10);
            if (ans<0)  ans += 10;
            return dmn[l][r][1] = ans;
        }
        else
        {
            long long ans(INT_MAX);
            for(int c(l);c<r;++c)
                for(int ks(1);ks<k;++ks)
                {
                    if(ks<=c-l+1 && k-ks<=r-c)
                    ans = min(ans,fmn(l,c,ks)*fmn(c+1,r,k-ks));
                }
            return dmn[l][r][k]=ans;
        }
    }
}
long long fmx(int l,int r,int k) //最小值
{
    if(dmx[l][r][k]!=-1)	return dmx[l][r][k];
    else
    {
        if(k==1)
        {
            int ans((s[r]-s[l-1])%10);
            if (ans<0)  ans += 10;
            return dmx[l][r][1] = ans;
        }
        else
        {
            long long ans(0);
            for(int c(l);c<r;++c)
                for(int ks(1);ks<k;++ks)
                {
                    if(ks<=c-l+1 && k-ks<=r-c)
                    ans = max(ans,fmx(l,c,ks)*fmx(c+1,r,k-ks));
                }
            return dmx[l][r][k] = ans;
        }
    }
}
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i(1);i<=n;++i)
        scanf("%d",s+i),s[i+n]=s[i];
    memset(dmn,-1,sizeof dmn);
    memset(dmx,-1,sizeof dmx);
    for(int i(1);i<2*n;++i)	s[i] += s[i-1]; //前缀和优化区间和
    long long Min(INT_MAX),Max(0); //寻找最优解
    for(int i(1);i<=n;++i)
    {
        Min = min(Min,fmn(i,i+n-1,m));
        Max = max(Max,fmx(i,i+n-1,m));
    }
    cout << Min << endl << Max;
    return 0;
}