0%

7.18夏令营总结

今天,我们并没有学习什么新知识,只是对昨天的知识复习了一下,并做了一些练习。

取数游戏

【题目】小明和小红在玩游戏,现在有一列数,每一个人轮流从两边取数,知道取玩。那么每人的分数就是他所取的数之和。小明先取,问能赢小红多少分?

【输入】

5

6 5 7 8 4

【输出】

4

【思路】一排数列,小明可以从两头取,去那边好呢?我们假设F[i][j]表示从i到j的数列小明可以赢多少。若取左边,那么子问题就成了F[i+1][j];若取右边,则子问题就变成了F[i][j-1],那么,很明显这是区间DP了。

就像石子归并一样,以长度分阶段,而状态转移方程也分析出来了,就是

F[i][j]=max(a[i]-F[i+1][j],a[j]-F[i][j-1])

也许有人会疑问,为什么要用a[i]减去F[i+1][j]呢?因为,F[i][j]是表示i到j小明赢多少,去了左边,接下来小红就得去一个,小明就赢不了F[i+1][j]的分数了,反而要输去,所以要减去。去右边的情况也同理。

【程序】

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
#include <fstream>
using namespace std;

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

#define maxn 1000

int num[maxn],F[maxn][maxn],n;

int main() {
fin >> n;
for (int i=0; i!=n; ++i)
fin >> num[i];//输入

for (int i=0; i!=n; ++i)
F[i][i]=num[i];//对于只有一个数,小明拿了这一个数,就赢得了,这一个数字

for (int len=2; len<=n; len++)//长度来分阶段
for (int l=0; l<=n-len; l++) {//枚举左端点
int r=l+len-1;//枚举右端点
F[l][r]=max(num[l]-F[l+1][r],num[r]-F[l][r-1]);//状态转移方程
}

fout << F[0][n-1] << endl;//输入
return 0;
}

能量项链

【题目】有N颗珠子连在一起,成为一条项链。没颗珠子都有有个标记(数字),每颗珠子的头标记是前一颗珠子的尾标记,每颗珠子的尾标记是后一颗珠子的头标记,如[2,3][3,5][5,10][10,2]。相邻的两颗珠子可以可并成一颗珠子,并发出能量,如[2,3][3,5],那么能量值为235=30,直到只剩下一颗珠子。问最大发出的能量是多少?

【输入】
2 3 5 10

【输出】
710

【思路】这题目看上去很长,其实题意跟石子归并相差无几。难点只有一个,这是环形的。唤醒并不好处理,怎么办呢?

做好的办法就是化曲为直。将它铺成一条直线,复制一段在后边,然后分段进行区间DP,如图:

他不见了。

这时,模块化的有点就凸显出来了,把一段区间DP做成一个模块,就更好了。

Tips:其实,我们可以开一个数组,每一个节点都贮存它的头标记和尾标记,虽然有点麻烦,但是在做区间DP时,计算会更加清晰。

【程序】

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
#include <fstream>
using namespace std;

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

#define double_maxn 200+20

struct {
int l,r;
}pearl[double_maxn]; //储存成,有头标记和尾标记的形式

int n;
long long maxx=-10000000;
long long F[double_maxn][double_maxn];

void read() {
fin >> n;
int tmp[double_maxn];
for (int i=0; i!=n; ++i)
fin >> tmp[i];

for (int i=0; i!=n-1; ++i) {
pearl[i].l=tmp[i];
pearl[i].r=tmp[i+1];
}

pearl[n-1].l=tmp[n-1];
pearl[n-1].r=tmp[0];//转化成,储存头标记和尾标记的形式,特别的要注意最后一个珠子的尾标记
}

void perpare() {
for (int i=0; i!=n; ++i)
pearl[i+n]=pearl[i];//复制一段在后面
}

long long work(int x, int y) {
for (int h=0; h<=double_maxn; h++)
for (int g=0; g<=double_maxn; g++)
if (h==g) F[h][g]=0;
else F[h][g]=-100000000;//初始化,赋值为负无穷

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]=max(F[L][R],F[L][mid]+F[mid+1][R]+pearl[L].l*pearl[mid].r*pearl[R].r);//状态转移方程
}

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

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

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

perpare();//储存头标记和尾标记

for (int t=0; t!=n; ++t) {
long long tmp=work(t,t+n);//做一次区间DP
maxx=max(maxx,tmp);
}

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