study record

ex

学习记录

突发奇想的问题：

  1. 证明《高能玩家》里面的博弈问题是否具有必胜策略，我猜没有。
  2. cf contest 1114 C 十进制该怎么做？

2019.2.9 线性dp

poj2279

题意

给定n行，每行最多站$a_i$个人，从左到右，从上到下依次要从矮到高。问方案数。

题解

设计状态$F(a_1, a_2, a_3, a_4, a_5)$表示此刻站了$(a_1, a_2, a_3, a_4, a_5)$个人数的方案数。

初始状态$F(0, 0, 0, 0, 0) = 1$.

所有人从矮到高依次的安排，因此满足的条件是前面排的人数必须大于等于后面的。

具体的转移方程看后面的代码，还是比较的清晰明了的。

我们设计状态的时候，都假设的是5行。当不满5行的时候，就用0来填，这也是一个比较重要的设计状态的思路，而不用分类讨论。

RE 代码, 思路是对的，但是写的有问题

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 31;
int ans[maxn][maxn][maxn][maxn][maxn];
int i, j, k, m, n;
int a[maxn];
void init(){
    for(int i=0; i<a[1]; i++)
        for(int j=0; j<=a[2]; j++)
            for(int k=0; k<=a[3]; k++)
                for(int m=0; m<=a[4]; m++)
                    for(int n=0; n<=a[5]; n++) ans[i][j][k][m][n] = 0;
}
int main(){
    int n;
    while(~scanf("%d", &n)){
       if(n == 0) break;
       for(int i=1; i<=n; i++) scanf("%d", &a[i]);
       for(i=n+1; i<=5; i++){
            a[i] = 0;
       }
       init();
       ans[0][0][0][0][0] = 1;
       for(i=0; i<=a[1]; i++){
            for(j = 0; j<=a[2]; j++){
                if(j>i) continue;
                for(k=0; k<=a[3]; k++){
                    if(k>j||k>i) continue;
                    for(m=0; m<=a[4]; m++){
                        if(m>i||m>j||m>k) continue;
                        for(n=0; n<=a[5]; n++){
                            if(n>i||n>j||n>k||n>m) continue;
                            if(i+1<=a[1]) ans[i+1][j][k][m][n] += ans[i][j][k][m][n];
                            if(j+1<=a[2]&&j<i) ans[i][j+1][k][m][n] += ans[i][j][k][m][n];
                            if(k+1<=a[3]&&k<i&&k<j) ans[i][j][k+1][m][n] += ans[i][j][k][m][n];
                            if(m+1<=a[4]&&m<i&&m<j&&m<k) ans[i][j][k][m+1][n] += ans[i][j][k][m][n];
                            if(n+1<=a[5]&&n<i&&n<j&&n<k&&n<m) ans[i][j][k][m][n+1] += ans[i][j][k][m][n];
                        }
                    }
                }
            }
       }
        printf("%d\n", ans[a[1]][a[2]][a[3]][a[4]][a[5]]);
    }
    return 0;
}

TYVJ 1071

题意

LCIS：求最长上升公共子序列

LCS最优的复杂度：$O(nlogn)$

LIS最优的复杂度：$O(n)$

题解

设计状态$F(i, j) 表示a[1]\dots a[i]和b[1]\dots b[j]构成的LCIS, b[j]为LCIS的结尾$，

$if \quad a[i] = b[j], F(i, j) = max_{0\le k<j, b_k<b_j}{F(i-1, k)+1}$

正常的$O（n^3）$扫描就行了。

由于答案的规模是在不断的增加的，所以可以优化。

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3+10;
const int inf = 1e9+10;
int f[maxn][maxn];
int a[maxn], b[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    {
        a[0] = b[0] = -inf;
        for(int i=1; i<=n; i++) scanf("%d", &a[i]);
        for(int i=1; i<=n; i++) scanf("%d", &b[i]);
        int val = 0;
        for(int i=1; i<=n; i++){
            val = f[i-1][0];
            for(int j=1; j<=n; j++){
                if(a[i] == b[j]) f[i][j] = val+1;
                else f[i][j] = f[i-1][j];
                if(b[j]<a[i]) val = max(val, f[i-1][j]);
            }
        }
        int ans = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) ans = max(ans, f[i][j]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

TYVJ 1061

题意

有三个服务员，初始的位置分别在1, 2, 3

现在他们有N个服务，每次从$i$到$j$节点的花费用一个矩阵$cost[i][j]$表示

任何一个节点不能有两个及以上的服务员

问最小的花费该如何安排

题解

设计下面的状态：

$F(i, x, y, z)$ 表示的是服务完$i$节点三个服务员的坐标为$(x, y, z)$

那么状态转移方程为：

我们可以缩小一维状态表示，因为知道哪两个位置没动，就能知道哪个位置移动到了目标位置

注意代码里面表示两个没有移动的位置（不知道自己的思路为什么有问题，记录第一个第二个人的位置）

会MLE，所以要用滚动数组。

ac code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int ans[2][205][205];
int request[2005];
int cost[205][205];
int pos[maxn];
int main()
{
    int l, n;
    scanf("%d%d", &l, &n);
    for(int i=1; i<=l; i++) for(int j=1; j<=l; j++) scanf("%d", &cost[i][j]);
    memset(ans, 0x3f, sizeof(ans));
    ans[0][1][2] = 0;
    request[0] = 3;
    for(int i=1; i<=n; i++) scanf("%d", &request[i]);
    int i, j, k;
    for(i=1; i<=n; i++){
        for(j=1; j<=l; j++){
            for(k=1; k<=l; k++){
                if(ans[i-1&1][j][k] != 0x3f3f3f3f){
                    //这里要填request[i-1]而不是request[i]!感觉是不动的两个人能推出第三个移动的人
                    ans[i&1][request[i-1]][k] = min(ans[i&1][request[i-1]][k],
                                                ans[i-1&1][j][k]+cost[j][request[i]]);
                    ans[i&1][j][request[i-1]] = min(ans[i&1][j][request[i-1]],
                                                ans[i-1&1][j][k]+cost[k][request[i]]);
                    //不能选择的，而是必须得移动，要服务客户
                    //这个方程有问题
                    ans[i&1][j][k] = min(ans[i&1][j][k],
                                       ans[i-1&1][j][k]+cost[request[i-1]][request[i]]);
                }
                ans[i-1&1][j][k] = 0x3f3f3f3f;
            }
        }
    }
    int lst = 1e9+10;
    for(int i=1; i<=l; i++){
        for(int j=1; j<=l ;j++){
            lst = min(lst, ans[n&1][i][j]);
        }
    }
    printf("%d\n", lst);
    return 0;
}
//#include<iostream>
//#include<cstdio>
//#include<cstring>
//#include<algorithm>
//using namespace std;
//int f[100][210][210],p[1010],c[210][210];
//int n,m;
//int main()
//{
//	cin>>m>>n;
//	for(int i=1;i<=m;i++)
//		for(int j=1;j<=m;j++)
//			cin>>c[i][j];
//	for(int i=1;i<=n;i++) cin>>p[i];
//	p[0]=3;
//	memset(f,0x3f,sizeof(f));
//	f[0][1][2]=0;
//	for(int i=1;i<=n;i++)
//		for(int x=1;x<=m;x++)
//			for(int y=1;y<=m;y++)
//				if(f[i-1][x][y]!=0x3f3f3f3f)
//				{
//					int z=p[i-1];
//					f[i][z][]=min(f[i][y][z],f[i-1][x][y]+c[x][p[i]]);
//					f[i][x][z]=min(f[i][x][z],f[i-1][x][y]+c[y][p[i]]);
//					f[i][x][y]=min(f[i][x][y],f[i-1][x][y]+c[z][p[i]]);
//
//				}
//	int ans=1<<30;
//        for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++){
//            for(int k=1; k<=m; k++){
//                cout<<f[i][j][k]<<" ";
//            }
//            cout<<endl;
//        }
//        cout<<endl<<endl;
//    }
//	for(int x=1;x<=m;x++)
//		for(int y=1;y<=m;y++)
//			ans=min(ans,f[n][x][y]);
//	cout<<ans<<endl;
//}

2019.2.10 区间dp

金字塔

link

题意

给定一个字符串的序列，问能够构造几个树形结构。

树形结构为前序遍历的序列。

题解

1
ABABABA

A|B|ABABA为例

A为根，B为一个子树，后面的一部分为另外的一棵子树

可以列出下面的转移方程

$F(l, r) = \begin{cases}
0 & \text{ if } s[l]!=s[r] \
\sum_{l+2\le k < r} F(l+1, k-1)*F(k, r) & \text{ if } s[l]=s[r]
\end{cases}$

递归+记忆化

ac code

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 305;
const int mod = 1e9;
int ans[maxn][maxn];
char s[maxn];
int n;
int solve(int l, int r){
    if(l>r) return 0;
    if(l == r) return 1;
    if(ans[l][r] != -1) return ans[l][r];
    ans[l][r] = 0;
    if(s[l]!=s[r]) return ans[l][r];
    for(int i=l+2; i<=r; i++){
        ans[l][r] = (ans[l][r] + (ll)solve(l+1, i-1)*solve(i, r)%mod)%mod;
    }
    return ans[l][r];
}
int main()
{
    ios::sync_with_stdio(false);
    while(~scanf("%s", s+1)){
        memset(ans, -1, sizeof(ans));
        n = strlen(s+1);
        solve(1, n);
        printf("%d\n", ans[1][n]);
    }
    return 0;
}

Polygon

题意

给一个n边形，每个顶点有一个数，每条边有一个操作数

每次删去一条边就能合并两个点，问如何合并使得最后的数字最大？

题解

因为是圈，再延长一倍使得复杂度降低

当 op 是加号的时候：

$F{max}(l, r) = max{l\le k<r}\begin{cases}
F{max}(l, k-1) op F{max}(k, r)\
F{min}(l, k-1) op F{min}(k, r)
\end{cases}$

当op是乘号的时候：

$F{min}(l, r) = min \begin{align*}
&= F{min}(l, k-1) op F{min}(k, r) \
&= F{min}(l, k-1) op F{max}(k, r)\
&= F{max}(l, k-1) op F_{min}(k, r)
\end{align*}$

debug了半天发现是读入问题。。。

ac code

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
//t +
//x *
//f保存的是最大值，f1保存的是最小值
int f[maxn][maxn], f1[maxn][maxn];
int a[maxn];
char b[maxn];
int n;
void init(){
    memset(f, -0x3f, sizeof(f));
    memset(f1, 0x3f, sizeof(f1));
}
int main()
{
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    getchar();
    init();
    for(int i=1; i<=n; i++){
        scanf("%c %d", &b[i], &a[i]);
        getchar();
        a[i+n] = a[i], b[i+n] = b[i];
    }
//    for(int i=1; i<=n; i++){
//        cout<<a[i]<<" "<<b[i]<<" |";
//    }
//    cout<<endl;
    for(int i=1; i<=2*n; i++) f[i][i] = f1[i][i] = a[i];
    for(int l=2; l<=n; l++){
        for(int i=1; i+l-1<=2*n; i++){
            for(int j=i+1; j<=i+l-1; j++){
                if(b[j] == 't'){
                    f[i][i+l-1] = max(f[i][i+l-1], f[i][j-1]+f[j][i+l-1]);
                    f1[i][i+l-1] = min(f1[i][i+l-1], f1[i][j-1]+f1[j][i+l-1]);
                }
                else{
                    f[i][i+l-1] = max(f[i][i+l-1], f[i][j-1]*f[j][i+l-1]);
                    f[i][i+l-1] = max(f[i][i+l-1], f1[i][j-1]*f1[j][i+l-1]);
                    f1[i][i+l-1] = min(f1[i][i+l-1], f1[i][j-1]*f[j][i+l-1]);
                    f1[i][i+l-1] = min(f1[i][i+l-1], f[i][j-1]*f1[j][i+l-1]);
                    f1[i][i+l-1] = min(f1[i][i+l-1], f1[i][j-1]*f1[j][i+l-1]);
                }
            }
        }
    }
    int mx = -0x7fffffff;
    for(int i=1; i+n-1<=2*n; i++) mx = max(mx, f[i][i+n-1]);
    printf("%d\n", mx);
    for(int i=1; i<=n; i++){
        if(f[i][i+n-1] == mx) printf("%d ", i);
    }
    printf("\n");
    return 0;
}

石子合并的问题

因为是一个比较的经典的问题就不写了，一个进阶的版本就是xdoj的生命的祭坛。

注意区间合并的特征就可以了。

未解决的问题

本文标题:study record

文章作者:Babydragon

发布时间:2019-02-09, 10:38:24

最后更新:2019-02-10, 23:06:48

原始链接:http://baolintian.github.io/2019/02/09/study-record/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2019.2.9 线性dp
    1. 1.1. poj2279
      1. 1.1.1. 题意
      2. 1.1.2. 题解
      3. 1.1.3. RE 代码, 思路是对的，但是写的有问题
    2. 1.2. TYVJ 1071
      1. 1.2.1. 题意
      2. 1.2.2. 题解
      3. 1.2.3. ac code
    3. 1.3. TYVJ 1061
      1. 1.3.1. 题意
      2. 1.3.2. 题解
      3. 1.3.3. ac code
  2. 2. 2019.2.10 区间dp
    1. 2.1. 金字塔
      1. 2.1.1. 题意
      2. 2.1.2. 题解
      3. 2.1.3. ac code
    2. 2.2. Polygon
      1. 2.2.1. 题意
      2. 2.2.2. 题解
      3. 2.2.3. ac code
    3. 2.3. 石子合并的问题
  • 未解决的问题
    • {{ live2d() }}