F - 数塔

经典问题,数塔。
使用动态规划解决问题的(最重要)前提是:

  1. 问题具有最优子结构
  2. 最优子结构的状态可以记录


例如上图中,以第二层$12$为顶层的数塔就是一个最优子结构。
再回到原来的顶层,想得到最终的结果只需要知道第二层两个子结构能得到的最大和,这是可记录的。
所以,我们从底层往顶层进行动态规划就可以了。

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
#include <bits/stdc++.h>
using namespace std;
int a[111][111];
int main()
{
int T,n;
scanf("%d",&T);
while (T--) {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
for (int j=1;j<=i;j++) {
scanf("%d",&a[i][j]);
}
}
for (int i=n-1;i>=1;i--) {
for (int j=1;j<=i;j++) {
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
}
}
printf("%d\n",a[1][1]);
}
return 0;
}

G - 免费馅饼

可以发现时刻的范围不是很大,把每个时刻看作每一层,这个问题就是三条边的数塔。
代码中平移一下是为了避免越界问题。

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 <bits/stdc++.h>
using namespace std;
const int N=100010;
int dp[N][13];
int main()
{
int n;
while (scanf("%d",&n),n) {
memset(dp,0,sizeof(dp));
int m=0;
for (int i=1;i<=n;i++) {
int x,t;
scanf("%d%d",&x,&t);
++dp[t][x+1];
m=max(m,t);
}
for (int i=m;i>=0;i--) {
for (int j=1;j<=11;j++) {
dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);
}
}
printf("%d\n",dp[0][6]);
}
return 0;
}

A - 饭卡

首先排除余额已经少于$5$的情况,然后分为$m-5$和$5$两部分,前面的$m-5$是个01背包问题,后面的$5$用来买最后一次。若用$dp(x)$表示$x$能买到的最大价值,那么答案为$m-dp(m-5)-a_i (1\le i\le n)$。
可以证明,最后买最贵的是最优的。比较复杂,这里仅通过$m-dp(m-5)-a_p$这个式子简要说明,如果最后买的不是最贵的,即 $p’ \neq p$:

  • $a_{p’}\le a_{p}$
  • 背包的物品集合加入了一个体积大的,去掉了一个体积小的;又有价值跟体积的值相等,所以$dp’(m-5)\le dp(m-5)$

两个减数都减小,最后的结果只会变大。

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
#include <bits/stdc++.h>
using namespace std;
const int N=1100;
int a[N],dp[N];
int main()
{
int n,m;
while (scanf("%d",&n),n) {
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
scanf("%d",&m);
if (m<5) {
printf("%d\n",m);
} else {
int p=max_element(a+1,a+n+1)-a;
m-=5;
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++) {
if (i==p) continue;
for (int j=m;j>=a[i];j--) {
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
}
}
printf("%d\n",m+5-dp[m]-a[p]);
}
}
return 0;
}

B - Piggy-Bank

已知存钱罐的确切重量,问最小可能价值。是恰好型的完全背包。
稍微讲一下完全背包一维的转移方程:
$$dp(j)=max(dp(j),dp(j-w_i)+v_i)$$ $j$从小到大枚举时,由于之前的$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
#include <bits/stdc++.h>
using namespace std;
const int M=10010;
const int INF=0x3f3f3f3f;
int dp[M];
int main()
{
int T,n,m;
scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&m);
m-=n;
memset(dp,INF,sizeof(dp));
dp[0]=0; scanf("%d",&n);
for (int i=1;i<=n;i++) {
int p,w;
scanf("%d%d",&p,&w);
for (int j=w;j<=m;j++) {
dp[j]=min(dp[j],dp[j-w]+p);
}
}
if (dp[m]==INF) {
puts("This is impossible.");
} else {
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]);
}
}
return 0;
}

C - Investment

给出本金、很多种债券和各自的利息,问$y$年以后最多能有多少钱,抽象一下就是做$y$次完全背包。
但是这题里面容量太大了做不了完全背包,所以题目里又给了一个条件,债券的价格都是$1000$的整数倍,那么直接把本金除以$1000$当作背包容量就行了,重复做$y$次。

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
#include <bits/stdc++.h>
using namespace std;
int w[22],v[22];
int dp[50000];
int main()
{
int T;
scanf("%d",&T);
while (T--) {
int n,M,Y;
scanf("%d%d",&M,&Y);
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d%d",&w[i],&v[i]);
w[i]/=1000;
}
while (Y--) {
int m=M/1000;
memset(dp,0,sizeof(dp));
for (int i=1;i<=n;i++) {
for (int j=w[i];j<=m;j++) {
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
M+=dp[m];
}
printf("%d\n",M);
}
return 0;
}

D - Common Subsequence

经典问题,最长公共子序列。
子串与子序列
设$C(i,j)$为$x_{1\dots i}$和$y_{1\dots j}$的最长公共子序列的长度,那么有:
$$\large C(i,j)=\begin{cases}
0 & \text{$i=0$ or $j=0$} \\
C(i-1,j-1)+1 & i,j\gt 0, x_i=y_j \\
max(C(i,j-1),C(i-1,j)) & i,j \gt 0, x_i\neq y_j
\end{cases}$$ 第一种情况很好理解。第二种情况就是$x_i$和$y_j$用来匹配了,所以等于了这两个都不用的情况$C(i-1,j-1)$加$1$。第三种情况就是不用$x_i$或者不用$y_j$取一个最大值。
其实第三种是最基本的情况,但是由于$max(C(i,j-1),C(i-1,j))$不会比$C(i-1,j-1)+1$更优(为什么?),所以第二种情况中可以不考虑第三种。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
char a[1010],b[1010];
int dp[1010][1010];
int main()
{
while (scanf("%s%s",a+1,b+1)!=EOF) {
int n=strlen(a+1);
int m=strlen(b+1);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
printf("%d\n",dp[n][m]);
}
return 0;
}

E - Max Sum

经典问题,最大子列和。(连续子序列,相当于子串)
状态转移方程也比较简单:
$$dp(i)=max(dp(i-1)+a[i],a[i])=max(dp(i-1),0)+a[i]$$ 分别对应两种情况:

  1. 接在上一次序列的后面
  2. 开始一个新的序列

输出的字典序最小意味着左端点和右端点都要最小。如果先记录右端点再反向计算左端点,那么:

  • $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
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
const int INF=1<<28;
int a[N],f[N];
int main()
{
int T,n,cas=0;
scanf("%d",&T);
while (T--) {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
int ans=-INF,p,q;
for (int i=1;i<=n;i++) {
f[i]=max(f[i-1],0)+a[i];
if (f[i]>ans) {
ans=f[i];
q=i;
}
}
int now=0;
for (int i=q;i>=1;i--) {
now+=a[i];
if (now==ans) p=i;
}
printf("Case %d:\n",++cas);
printf("%d %d %d\n",ans,p,q);
if (T) puts("");
}
return 0;
}

H - 不要62

常见$dp$类型:数位$dp$。可以使用数位$dp$的$dfs$型模板,原理自行查阅。
ps. 这题数据量比较小,可以预处理$O(1)$回答,但是大家还是要好好学习数位$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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int D=22;
int dig[D];
ll f[D][10][2];
ll dfs(int pos,int pre,int fg,int limit)
{
if (pos<0) return fg==0;
if (!limit&&f[pos][pre][fg]!=-1) {
return f[pos][pre][fg];
}
ll res=0;
int last=limit?dig[pos]:9;
for (int i=0;i<=last;i++) {
res+=dfs(pos-1,i,fg||(pre==6)&&(i==2)||i==4,limit&&(i==last));
}
if (!limit) f[pos][pre][fg]=res;
return res;
}
ll solve(ll n)
{
int len=0;
while (n) {
dig[len++]=n%10;
n/=10;
}
return dfs(len-1,-1,0,1);
}
int main()
{
int n,m;
while (scanf("%d%d",&n,&m)!=EOF) {
if (!n&&!m) break;
memset(f,-1,sizeof(f));
printf("%lld\n",solve(m)-solve(n-1));
}
return 0;
}

I - Unidirectional TSP

常见$dp$类型:网格图$dp$。如果不考虑上下可以穿越,那么转移方程非常简单:
$$dp(i,j)=min(dp(i-1,j-1),dp(i,j-1),dp(i+1,j-1))$$ 上下可以穿越时,需要根据$i$的值特殊处理一下,代码里用的是三目表达式。
因为题目要求输出路径,所以用$a_i$储存前一列可以转移过来的行号,又因为题目里要求字典序最小,所以先排个序,之后按照顺序更新,并约定值相等的不能更新

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 <bits/stdc++.h>
using namespace std;
const int N=110,INF=1<<28;
int dp[N][N],pre[N][N];
int main()
{
int n,m;
while (scanf("%d%d",&n,&m)!=EOF) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
scanf("%d",&dp[i][j]);
}
}
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
int a[3]={i};
a[1]=(i==1)?n:i-1;
a[2]=(i==n)?1:i+1;
sort(a,a+3);
int x=INF,y=-1;
for (int k=0;k<3;k++) {
if (dp[a[k]][j-1]<x) {
x=dp[y=a[k]][j-1];
}
}
dp[i][j]+=x;
pre[i][j]=y;
}
}
int x=INF,y=-1;
for (int i=1;i<=n;i++) {
if (dp[i][m]<x) {
x=dp[y=i][m];
}
}
stack<int> st;
for (int j=m;j>=1;j--) {
st.push(y);
y=pre[y][j];
}
bool fi=true;
while (!st.empty()) {
if (fi) {
printf("%d",st.top());
fi=false;
} else {
printf(" %d",st.top());
}
st.pop();
}
printf("\n%d\n",x);
}
return 0;
}

J - DZY Loves Sequences

常见类型:扫一遍预处理。分别求出向左和向右最多可以延伸的长度,然后对于每一个$a_i$:

  • 如果$a_{i-1} + 1 \lt a_{i+1}$,那么$a_i$可以修改为$a_{i-1}$和$a_{i-1}$之间的某个数使得左右两段连接在一起
  • 如果$a_{i-1} + 1 \ge a_{i+1}$,那么$a_i$只能修改为比$a_{i-1}$大或者比$a_{i-1}$小的数,即左长度加一或者右长度加一
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
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int a[N],l[N],r[N];
int main()
{
int n;
scanf("%d",&n);
for (int i=1;i<=n;i++) {
scanf("%d",a+i);
}
l[1]=1;
for (int i=2;i<=n;i++) {
if (a[i-1]<a[i]) l[i]=l[i-1];
else l[i]=i;
}
r[n]=n;
for (int i=n-1;i;i--) {
if (a[i]<a[i+1]) r[i]=r[i+1];
else r[i]=i;
}
int ans=0;
for (int i=1;i<=n;i++) {
l[i]=i-l[i]+1;
r[i]=r[i]-i+1;
ans=max(ans,max(l[i],r[i]));
}
for (int i=1;i<=n;i++) {
if (a[i-1]+1<a[i+1]) {
ans=max(ans,l[i-1]+1+r[i+1]);
} else {
ans=max(ans,max(l[i-1]+1,r[i+1]+1));
}
}
printf("%d\n",ans);
return 0;
}