0%

7.19夏令营总结

今天,我们仍然是做题目,深入动态规划,而我,则着重于区间动态规划。虽然今天只做了一道题,但对于这道题,我认为还是有些难度的。

数字游戏

【题目】在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。游戏的要求是使你所得的k最大或者最小。

2

4

-1

3

例如,对于下面这圈数字(n=4,m=2):
2013年07月22日 - 邱俊斌 - 邱俊斌
当要求最小值时,((2-1) mod 10)×((4+3) mod 10)=1×7=7,要求最大值时,为((2+4+3) mod 10)×(-1 mod 10)=9×9=81。特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。

求最大值和最小值。

【输入】

4 2

4

3

-1

2

【输出】

7

81

【分析】看上去,这一道题似乎无从下手。但明显的,我们知道这一道题目,我们可以用动态规划来下手。但是,而动态规划的核心,就在于子问题。

在不考虑环形结构的情况下,以样例为例[4,3,-1,2],因为我们要把这4个数分成两份,所以

我们可以单独把[4]分1份,那么[3,-1,2]分成1份,就是子问题(下图红色部分),

也可以把[4,3]分1份,那么[-1,2] 分成1份,就是子问题(下图蓝色部分),

也可以把[4,3,-1]分1份,那么[2] 分成1份,就是子问题(下图绿色部分)。

他不见了。

子问题是解决了,那么状态转移方程也可以列出来了,按照石子归并的方法,用F[i][j]表示从i到j的m个区间的最大值(最小值)。但是,我们总觉得少了什么东西,就是如何表示它的份数呢?

没错,我们需要开多一维(事实上,我们可以优化掉的),F[i][j][k]表示从第i位到第j位,分成k个区间的最大值,或最小值,由上可知状态转移方程,如下:

sum[i][j]表示从第i位到第j位的总和后,模10,如果模10后为负数,应自加10。

对于环形的问题,我们完全可以用能量项链的方法,复制一段在数据后面,每一段都进行一次DP。

接下来要注意的就是

① 就像石子归并,以长度分阶段,枚举左端点,确定右端点

② sum[i][j]可以预处理,sum[i][j]=sum[i][j-1]+num[j],sum[0][0]=num[0]。

③ DP前,如果是求最大值,那么DP数组F应清为负无穷,求最小值则相反

④ 当区间为1时,F[i][j][1]=sum[i][j]

⑤ 疑问:在DP时,为什么枚举区间K时,要放在最外层,

1
2
3
4
5
6
7
8
for (int K=2;K<=m; K++)
for (int len=K; len<=n; len++)
for (int L=x; L<=n-len+x; L++) {
int R=L+len-1;

for (int mid=L; mid!=R; mid++)
F[L][R][K]=max(F[L][R][K],F[mid+1][R][K-1] * sum[L][mid]);
}

而不能放在循环最四层

1
2
3
4
5
6
7
for (int len=K; len<=n; len++)
for (int L=x; L<=n-len+x; L++) {
int R=L+len-1;
for (int mid=L; mid!=R; mid++)
for (int K=2;K<=(len-mid+1) && K<=m; K++)
F[L][R][K]=max(F[L][R][K],F[mid+1][R][K-1] * sum[L][mid]);
}(实践可以)

【程序】

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <fstream>
using namespace std;

ifstream fin("Game.in");
ofstream fout("Game.out");

#define double_maxn 100+10
#define maxm 10
#define oo 100000000

int sum[double_maxn][double_maxn];
int num[double_maxn],n,m;
int F[double_maxn][double_maxn][maxm];
int maxx=-oo,minn=oo;

void read() {
fin >> n >> m;
for (int i=0; i!=n; ++i)
fin >> num[i];
}

void perpare() {
for (int i=0; i!=n; ++i)
num[i+n]=num[i];

sum[0][0]=num[0];
for (int i=0; i!=2*n; ++i)
for (int j=i; j!=2*n; ++j)
if (!(i==0 && j==0))
sum[i][j]=(sum[i][j-1]+num[j]);

for (int i=0; i!=2*n; ++i)
for (int j=i; j!=2*n; ++j) {
sum[i][j]=(sum[i][j]+oo) % 10;
}
}

int work1(int x, int y) {
for (int i=0; i!=2*n; ++i)
for (int j=i; j!=2*n; ++j) {
F[i][j][1]=sum[i][j];//区间为1时,实际上值为sum[i][j]
for (int k=2; k<=m; k++)
F[i][j][k]=-oo;//清为负无穷
}

for (int K=2;K<=m; K++)
for (int len=K; len<=n; len++)
for (int L=x; L<=n-len+x; L++) {
int R=L+len-1;
for (int mid=L; mid!=R; mid++)
F[L][R][K]=max(F[L][R][K],F[mid+1][R][K-1] * sum[L][mid]);//状态转移方程
}

return F[x][y-1][m];//返回
}

int work2(int x, int y) {
for (int i=0; i!=2*n; ++i)
for (int j=i; j!=2*n; ++j) {
F[i][j][1]=sum[i][j];
for (int k=2; k<=m; k++)
F[i][j][k]=oo; //清为正无穷
}

for (int K=2;K<=m; K++)
for (int len=2; len<=n; len++)
for (int L=x; L<=n-len+x; L++) {
int R=L+len-1;
for (int mid=L; mid!=R; mid++)
F[L][R][K]=min(F[L][R][K],F[mid+1][R][K-1] * sum[L][mid]);
}

return F[x][y-1][m]; //返回
}

void write() {
fout << minn << endl;
fout << maxx << endl;
}

int main() {
read();//输入

perpare();//解决环形问题

for (int t=0; t!=n; ++t) {
int tmp1=work1(t,t+n);//求最大
int tmp2=work2(t,t+n);//求最小
maxx=max(maxx,tmp1);
minn=min(minn,tmp2);
}

write();//输出
return 0;
}

【优化】

① 其实,求最大最小值的DP,极为类似,我们可以优化成一段DP

② 求sum[i][j],我们可以用前缀和的方法,用ans[i]表示前i位的和,那么sum[i][j]=ans[j]-ans[i-1]。那么,空间上可以降一维,求和时,时间上,也可以降一维。

③ 其实,我们是先DP区间为2是的情况;然后再DP区间为3的情况……那么,我们完全可用滚动数组的方式,把F数组降一维。尽管那一维,只有10位,但是,这种思想有时是值得肯定的。

【优化程序】

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <fstream>
using namespace std;

ifstream fin("Game.in");
ofstream fout("Game.out");

#define double_maxn 100+10
#define oo 100000000

typedef int DP[double_maxn][double_maxn];

int num[double_maxn],sum[double_maxn];
int n,m;
DP maxF,minF,maxF_new,minF_new;
int maxx=-oo,minn=oo;

void read() {
fin >> n >> m;
for (int i=0; i!=n; ++i) {
fin >> num[i];
num[i]=(num[i]+oo) % 10;
}
}

void perpare() {
for (int i=0; i!=n; ++i)
num[i+n]=num[i];

sum[0]=num[0];
for (int i=1; i!=2*n; ++i)
sum[i]=(sum[i-1]+num[i]) % 10;
}

int get(int x, int y) {
if (x==y) return num[x];
else return (sum[y]-sum[x-1]+oo) % 10;
}//使用前缀和

int work(int x, int y, int &ans1, int &ans2) {
for (int i=x; i!=y; ++i)
for (int j=i; j!=y; ++j) {
maxF[i][j]=get(i,j);
minF[i][j]=get(i,j);
}

for (int K=2;K<=m; K++) {
for (int i=x; i!=y; ++i)
for (int j=i; j!=y; ++j) {
maxF_new[i][j]=-oo;
minF_new[i][j]=oo;
}//边界

for (int len=K; len<=n; len++)
for (int L=x; L<=n-len+x; L++) {
int R=L+len-1;
for (int mid=L; mid!=R; mid++) {
maxF_new[L][R]=max(maxF_new[L][R],maxF[mid+1][R] * get(L,mid));

minF_new[L][R]=min(minF_new[L][R],minF[mid+1][R] * get(L,mid));//状态转移方程
}
}

memcpy(maxF,maxF_new,sizeof(maxF));
memcpy(minF,minF_new,sizeof(minF));//更新滚动数组
}

ans1=maxF[x][y-1];
ans2=minF[x][y-1];
}

void write() {
fout << minn << endl;
fout << maxx << endl;
}

int main() {
read();

perpare();

for (int t=0; t!=n; ++t) {
int tmp1,tmp2;
work(t,t+n,tmp1,tmp2);

maxx=max(maxx,tmp1);
minn=min(minn,tmp2);
}

write();
return 0;
}
Thank you so much.