近期题单一览
时间：20201011~20201027
✔hdu1024，滚动数组练习
✔hdu3092，数论+完全背包
✔poj1170，状压背包
✔hdu4352，数位DP+LIS
✔hdu2476，区间DP
✔hdu4745，回文序列+区间DP
✔hdu2844，多重背包
✔hdu2089，数位DP入门
✔hdu3652，数位DP进阶
✔hdu1520，树形DP入门
✔hdu3001，状压DP入门
✔poj2411，铺砖（状压DP）
✔poj2096，概率DP（期望计算）
✔poj3071，概率DP（概率计算）
部分总结
嗯有些题后面还有个注释，那是前面推小状态的时候才写上去的思路。后面写草稿纸了就无代码注释了（雾）。
HDU1024
滚动数组优化，若无把握首先写出原方程，后再改为滚动数组，使用异或实现转移。
另外在滚动了数组后边界设置可能会有所变化，需要特别留意。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define maxn 1000005
#define int long long
using namespace std;
int m, n, a[maxn];
int dp[maxn][2];
signed main(void)
{
while(~scanf("%lld %lld", &m, &n))
{
memset(dp, 0xce, sizeof(dp));
dp[0][0] = dp[0][1] = 0;
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
int flag = 0;
for(int i = 1; i <= m; i++)
{
int maxx = -(1<<30);
for(int j = i; j <= n; j++)
{
maxx = max(maxx, dp[j-1][flag^1]);
if(j - 1 < i)
dp[j][flag] = maxx + a[j];
else
dp[j][flag] = max(dp[j-1][flag], maxx) + a[j];
}
flag ^= 1;
}
int ans = -(1<<30);
for(int i = m; i <= n; i++)
{
ans = max(ans, dp[i][flag^1]);
}
printf("%lld\n", ans);
}
return 0;
}
|
HDU3092
这题有一个非常妙的思想，创立一个dp数组用于状态的转移，一个计数的数组用于比较前后的大小
（小米ICPC热身赛也有类似的一题，不过我对数没考虑0的情况白给了一发）。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define maxn 3005
#define int long long
using namespace std;
int s, m;
int ans[maxn], pri[maxn], pnum[maxn];
double dp[maxn];
int gcd(int x, int y){
return y ? gcd(y, x % y) : x;
}
int lcm(int x, int y){
return x * y / gcd(x, y);
}
void init(){
memset(pri, true, sizeof(pri));
for(int i = 2; i <= 3000; i++)
{
for(int j = 2; pri[i] && j * j <= i; j++)
if(i % j == 0) pri[i] = false;
if(pri[i])
pnum[++pnum[0]] = i;
}
}
signed main(void)
{
init();
while(~scanf("%lld %lld", &s, &m))
{
memset(dp, 0, sizeof(dp));
for(int i = 0; i <= s; i++) ans[i] = 1;
for(int i = 1; i <= pnum[0] && pnum[i] <= s; i++)
{
for(int j = s; j >= pnum[i]; j--)
{
for(int k = pnum[i], c = 1; j - k >= 0; k *= pnum[i], c++)
{
if(dp[j] < dp[j - k] + c * log10(pnum[i]))
{
dp[j] = dp[j - k] + c * log10(pnum[i]);
ans[j] = ((ans[j - k] % m) * (k % m)) % m;
}
}
}
}
printf("%lld\n", ans[s]);
}
return 0;
}
|
POJ1170
一道状态压缩的题目，不过开始我直接莽了一波二进制状压，后面MLE了。在借鉴别人思路后写了个六进制状态压缩，成功过了这题。
后面还有一题类似思路的TSP，是每个地方最多去两次，使用三进制压缩即可状态转移。
如果进制转换比较麻烦，还可以直接用n位数代替，比如直接使用十进制下的66666（最大）来代替这题的六进制。
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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define maxn 10005
using namespace std;
int b, s, sum;
int con[maxn], cop[maxn], ctn[maxn], six[maxn], dp[maxn*10];
struct Product{
int c;
int k;
int p;
} p[maxn];
struct Com{
int c;
int k;
} co[maxn][maxn];
int calc(int x, int pos){
for(int i = b; i >= pos+1; i--)
if(x > six[i]) x %= six[i];
return x / six[pos];
}
int dfs(int sta){
if(dp[sta] < 1e9)
return dp[sta];
int maxx = (1<<30);
for(int i = 1; i <= s; i++)
{
int flag = 0;
for(int j = 1; j <= con[i]; j++)
{
if(p[ctn[co[i][j].c]].k - calc(sta, ctn[co[i][j].c]) < co[i][j].k)
{
flag = 1;
break;
}
}
if(flag) continue;
int plus = 0;
for(int j = 1; j <= con[i]; j++)
plus += co[i][j].k * six[ctn[co[i][j].c]];
maxx = min(maxx, dfs(sta + plus) + cop[i]);
}
for(int i = 1; i <= b; i++)
if(p[i].k - calc(sta, i) >= 1)
maxx = min(maxx, dfs(sta + six[i]) + p[i].p);
return dp[sta] = maxx;
}
int main(void)
{
memset(dp, 0x3f, sizeof(dp));
scanf("%d", &b);
int bas = 1, tp = 0;
for(int i = 1; i <= b; i++)
{
six[i-1] = bas;
scanf("%d %d %d", &p[i].c, &p[i].k, &p[i].p);
ctn[p[i].c] = i;
bas *= 6;
tp += bas*p[i].k;
}
six[b] = bas;
dp[tp] = 0;
scanf("%d", &s);
for(int i = 1; i <= s; i++)
{
scanf("%d", &con[i]);
for(int j = 1; j <= con[i]; j++)
scanf("%d %d", &co[i][j].c, &co[i][j].k);
scanf("%d", &cop[i]);
}
printf("%d\n", dfs(0));
return 0;
}
|
HDU4352
我第一道写的数位DP题，细节还是比较难搞。
其中有个很巧妙的思路，就是求解LIS的nlogn思路转化到二进制数位上面去，在下一个数位比上一个数位小的时候，
替换之（即代码中的(x ^ (1 << i)) | (1 << y)），留更多的机会给后面的数位。
这个压缩状态的思路还是挺难想的，要是比赛时能直接写出这种题目就好了。
另外就是数位DP一些基本需要维护的东西，目前枚举到的位置（由高到低），当前数位是否在前导零中，当前数位是否有限制，已经完成的状态（看各种题维护，这题因为是严格上升子序列所以用10位二进制数状态压缩维护了0-9是否出现，别的题比如不要62这种就是维护前面是否有出现过题目不允许的情况）。
然后，学姐的故事也蛮好看的，被XHXJ圈粉了XD。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define maxn (1<<10)
#define int long long
using namespace std;
int t, l, r, k, c;
int dp[25][maxn][25], cnt[maxn], dis[maxn], nxc[maxn][maxn];
int calc(int x, int y){
for(int i = y; i <= 9; i++)
if(x & (1 << i))
return (x ^ (1 << i)) | (1 << y);
return x | (1 << y);
}
void inits(){
memset(dp, -1, sizeof(dp));
for(int i = 0; i < (1 << 10); i++)
{
for(int j = 0; j <= 9; j++)
{
if(i & (1 << j)) cnt[i]++;
nxc[i][j] = calc(i, j);
}
}
}
int dfs(int len, int sta, int lim, int zero){
if(len <= 0) return cnt[sta] == k;
if(!lim && dp[len][sta][k] >= 0)
return dp[len][sta][k];
int res = 0;
int limm = lim ? dis[len] : 9;
for(int i = 0; i <= limm; i++)
res += dfs(len-1, (i == 0 && zero) ? sta : nxc[sta][i], lim && i == limm, zero && i == 0);
return lim ? res : dp[len][sta][k] = res;
}
int solve(int x, int k){
int len = 0;
while(x)
{
dis[++len] = x % 10;
x /= 10;
}
return dfs(len, 0, 1, 1);
}
signed main(void)
{
inits();
scanf("%lld", &t);
while(t--)
{
scanf("%lld %lld %lld", &l, &r, &k);
printf("Case #%lld: %lld\n", ++c, solve(r, k) - solve(l - 1, k));
}
return 0;
}
|
HDU2476
问的是从字符串A到字符串B通过区间赋值的操作最少需要多少步。
这题有一个关键点就是要再维护一个由空串到字符串B的最少操作步数，
然后，当AB串当前位相同则直接从前一位转移过来，
若AB串当前位不同，则枚举1~当前位-1，分为空串直接覆盖和从A转移到B两部分，以便进行状态转移。
怎么说呢，偶尔从A难以直接到B的时候，考虑从0开始，到B有多难，再讨论转移方程。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 1005
using namespace std;
int sum[maxn], dp[maxn][maxn];
char str1[maxn], str2[maxn];
int dfs(int lf, int rt){
if(rt < lf) return 0;
if(dp[lf][rt] < 1e9) return dp[lf][rt];
if(lf == rt)
return dp[lf][rt] = 1;
int minn = (1 << 30);
minn = min(minn, 1 + dfs(lf + 1, rt));
for(int k = lf + 1; k <= rt; k++)
if(str2[lf] == str2[k])
minn = min(minn, dfs(lf, k - 1) + dfs(k + 1, rt));
return dp[lf][rt] = minn;
}
int main(void)
{
while(~scanf("%s", str1+1))
{
memset(dp, 0x3f, sizeof(dp));
scanf("%s", str2+1);
int len = strlen(str1+1);
for(int i = 1; i <= len; i++) dfs(1, i);
sum[0] = 0;
for(int i = 1; i <= len; i++)
{
sum[i] = dp[1][i];
if(str1[i] == str2[i]) sum[i] = sum[i - 1];
else
{
for(int j = 1; j <= i - 1; j++)
sum[i] = min(sum[i], sum[j] + dp[j + 1][i]);
}
}
printf("%d\n", sum[len]);
}
system("pause");
return 0;
}
|
POJ2411
铺砖问题，经典状压DP。
这题难点在于状态的设置，横着的砖状态为【0，0】，竖着的砖状态为【1，0】，以这样的状态设计，便可以得到dp[n][0]一定是填充完毕的解。然后就是这一题的记忆化写起来会比较烦，偶尔还是直接递推状态转移方程会好些。
主要的收获还是如何设计一个状态转移方程，使其在结束时符合题意，并能够满足方便转移的条件。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 100005
using namespace std;
int n, m;
long long dp[15][maxn]; int ch[2050][2050];
bool check(int j, int k){
if(~ch[j][k] || ~ch[k][j]) return ch[j][k];
int cnt = 0, x = j | k;
for(register int i = 0; i <= m - 1; i++)
{
if(x & (1 << i))
{
if(cnt & 1) return ch[j][k] = ch[k][j] = 0;
}
else cnt++;
if(i == m - 1 && cnt & 1) return ch[j][k] = ch[k][j] = 0;
}
return ch[j][k] = ch[k][j] = 1;
}
signed main(void)
{
while(scanf("%d %d", &n, &m), n)
{
memset(ch, -1, sizeof(ch));
dp[0][0] = 1;
for(register int i = 1; i <= n; i++)
{
for(register int j = 0; j <= (1 << m) - 1; j++)
{
dp[i][j] = 0;
for(register int k = 0; k <= (1 << m) - 1; k++)
{
if(!(j & k) && check(j, k))
{
dp[i][j] += dp[i - 1][k];
}
}
}
}
printf("%lld\n", dp[n][0]);
}
system("pause");
return 0;
}
|
POJ2096 & POJ3071
POJ2096（期望)；
POJ3071（概率）。
概率DP的题目有很多很多，这里是入门两题。
然后又日常被POJ卡了一下精度…POJ的话果然还是用%f好些…
其中，期望我们一般设置由后往前推导$dp[n][m] = \dots$，再对表达式做一定的变形，使其不会在运算过程中因为某些问题除以$0$。
而概率我们一般设置由前往后推导，该题是以足球场数为例，$dp[i][j]$为第$i$场中$j$获胜的概率，其中每次$j$需要面对的敌人范围比较难做。我AC后瞄了一下，网上的都是一堆位运算…
感觉还是我这样维护多一个cnt和flag好写一些。
简而言之，就是一个由前往后，一个由后往前，这两个都是很常见的题型，务必重视。
POJ2096
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 1005
using namespace std;
int n, s;
double dp[maxn][maxn];
int main(void)
{
scanf("%d %d", &n, &s);
dp[n][s] = 0;
for(int i = n; i >= 0; i--)
for(int j = s; j >= 0; j--)
{
if(i == n && j == s) continue;
dp[i][j] = ( n * s +
(n - i) * j * dp[i + 1][j] +
i * (s - j) * dp[i][j + 1] +
(n - i) * (s - j) * dp[i + 1][j + 1] )
/ (1.0 * (n * s - i * j));
}
printf("%.4f\n", (double)dp[0][0]);
system("pause");
return 0;
}
|
POJ3071
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 2050
using namespace std;
int n, bas[maxn];
double mar[maxn][maxn], dp[maxn][maxn];
int main(void)
{
bas[1] = 2;
for (int i = 2; i <= 8; i++) bas[i] = bas[i - 1] * 2;
while (scanf("%d", &n), ~n)
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= bas[n]; i++)
for (int j = 1; j <= bas[n]; j++)
scanf("%lf", &mar[i][j]);
for (int j = 1; j <= bas[n]; j++)
dp[1][j] = j & 1 ? mar[j][j + 1] : mar[j][j - 1];
for (int i = 2; i <= n; i++)
{
int cnt = 0, flag = 0;
for (int j = 1; j <= bas[n]; j++)
{
cnt++;
if (!flag)
{
for (int k = j + bas[i - 1] - cnt + 1; k <= j + 2 * bas[i - 1] - cnt; k++)
dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * mar[j][k];
if (cnt == bas[i - 1])
cnt = 0, flag = 1;
continue;
}
if (flag)
{
for (int k = j - bas[i - 1] - cnt + 1; k <= j - cnt; k++)
dp[i][j] += dp[i - 1][j] * dp[i - 1][k] * mar[j][k];
if (cnt == bas[i - 1])
cnt = 0, flag = 0;
continue;
}
}
}
int pos = 0;
double maxx = 0;
for (int j = 1; j <= bas[n]; j++)
if (dp[n][j] > maxx)
maxx = dp[n][j], pos = j;
printf("%d\n", pos);
}
return 0;
}
|
下阶段目标
最近比赛有些多，一个是十一月准备天梯赛的L2类题目，另一个是回去复习一下简单贪心和分治的题目（以及某些能反悔的贪心，比如某CCPC的钓鱼），还有就是补一下最近的题了（比如前天的ICPC小米邀请赛，害，DP还是没写出来）。
大概先这些，DP类的题目基本上简单的都入了一下门，后面那些综合性很强的DP还是任重而道远。
【下一阶段的水题题单，需尽快完成】
hdu1050 活动安排变形
hdu4864 不错的题
poj1328 活动安排变形
poj1089 区间覆盖
hdu4911 逆序对
hdu1425 快速排序思想
还有一些较难的题目后面找一下再列，上面从黑书中选的题目主要是为了快速复习一下。
嘛，毕竟天梯赛没板子可以用。
搞完了贪心分治的简单复习，就要回去复习一下图论了。
还得学一下计算几何，前天比赛计算几何犹豫了，虽然思路都是对的但是没怎么写，白给了草。
kuangbin：人十我百，人百我万。