2022年8月学习记录 - 动态规划专练

2022-12-10 文章脱敏

  1. 文章脱敏：更改了部分字为错别字，用小括号扩出。

我的资料

NOI官网：简单动态规划

动态规划

  • 阶段：据空间顺序或时间顺序对问题的求解划分阶段。
  • 状态：描述事物的性质，不同事物有不同的性质，因而用不同的状态来刻画。对问题的求解状态的描述是分阶段的。
  • 决策：对于一个阶段的某个状态，从该状态演变到下一阶段的某个状态的选择。
  • 状态转移方程：用数学公式描述与阶段相关的状态间的演变规律。
  • 最优子结构：以每一步都是最优的来保证全局是最优的。
  • 无后效性：某阶段状态一旦确定。以后的决策就可以直接使用。舍弃的状态，不会在后续决策中被使用。
  • “动态”的含义：一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。

洛谷题单 动态规划的引入

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<string.h>
using namespace std;
int main(){
	int r=0;
	cin>>r;
	int map[r+2][r+2];
	memset(map,0,sizeof(map));
	for(int i=0;i<r;i++){
		for(int j=0;j<=i;j++){
			cin>>map[i][j];
		}
	}
	for(int i=r-1;i>=0;i--){
		for(int j=i;j>=0;j--){
			map[i][j]+=max(map[i+1][j],map[i+1][j+1]);
			//cout<<map[i][j]<<"(i="<<i<<",j="<<j<<") ";
		}
		//cout<<endl;
	}
	cout<<map[0][0]<<endl;
	return 0;
}

(单击上方的 < 展开代码)

P1434 [SHOI2002] 滑雪

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<string.h>
using namespace std;
int r=0,c=0,ans=0;
int map[105][105],longest[105][105],height[105][105];
int dx[5]={-1,0,1,0};
int dy[5]={0,1,0,-1};
int search(int x,int y){
	if(longest[x][y]<0){
		int maxLength=0;
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			if(nx>=0 && nx<=r && ny>=0 && ny<=c && map[x][y]<map[nx][ny]){
				int nextLength=search(nx,ny);
				if(maxLength<nextLength){
					maxLength=nextLength;
				}
			}
		}
		longest[x][y]=maxLength+1;
        //cout<<"x="<<x<<",y="<<y<<",maxLength="<<maxLength<<",longest="<<longest[x][y]<<endl;
	}
	return longest[x][y]; 
}
int main(){
	memset(map,0,sizeof(map));
	memset(longest,-1,sizeof(longest));
	memset(height,0,sizeof(height));
	cin>>r>>c;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			cin>>map[i][j];
		}
	}
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
            //cout<<search(i,j)<<"(i="<<i<<",j="<<j<<") ";
			if(ans<search(i,j)){
				ans=search(i,j);
			}
		}
        //cout<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

(单击上方的 < 展开代码)

P2196 [NOIP1996 提高组] 挖地(镭)

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
#include<iostream>
#include<string.h>
using namespace std;
struct node{
	int to,next;
}edge[25];
int head[25],cnt=0;
void add(int u,int v){
    edge[++cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt;
	return;
}
int dp[30],pre[30],s[30];
int n,w[30];
int dfs(int u,int fa){
    if(dp[u]==0){
    	for(int i=head[u];i!=0;i=edge[i].next){
    		int v=edge[i].to;
    		if(v==fa) continue;
    		dp[v]=dfs(v,u);
    		if(dp[u]<dp[v]){
    			dp[u]=dp[v];
    			pre[u]=v;
			}
		}
		dp[u]+=w[u];
	}
    return dp[u];
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
			int x;
			cin>>x;
			if(x>0) add(i,j);
		}
	}
	int ans=0,k;
	for(int i=1;i<=n;i++){
		memset(dp,0,sizeof(dp));
		int tmp=dfs(i,0);
		if(ans<tmp){
			ans=tmp;
			swap(pre,s);
			k=i;
		}
	}
	while(k!=0){
		cout<<k<<" ";
		k=s[k]; 
	}
	cout<<endl<<ans<<endl;
	return 0;
}

(单击上方的 < 展开代码)

P1048 [NOIP2005 普及组] 采药

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<iostream>
#include<string.h>
using namespace std;
int main(){
	int t,m;
	cin>>t>>m;
	int dp[m+2][t+2],v[m+2],w[m+2];
	memset(dp,0,sizeof(dp));
	memset(v,0,sizeof(v));
	memset(w,0,sTODOizeof(w));
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=t;j>=0;j--){
			if(j>=w[i]){
				dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
			}else{
				dp[i][j]=dp[i-1][j];
			}
		}
	}
	cout<<dp[m][t]<<endl;
	return 0;
}

(单击上方的 < 展开代码)

P1616 疯狂的采药

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<string.h>
#define ll long long
using namespace std;
int main(){
	ll t=0,m=0;
	cin>>t>>m;
	ll dp[t+2],w[m+2],v[m+2];
	memset(dp,0,sizeof(dp));
	memset(w,0,sizeof(w));
	memset(v,0,sizeof(v));
	for(int i=1;i<=m;i++){
		cin>>w[i]>>v[i];
	}
	for(int i=1;i<=m;i++){
		for(int j=w[i];j<=t;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[t];
	return 0;
}

(单击上方的 < 展开代码)

P1802 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
#include<iostream>
#define ll long long
const int MAXN=1002;
using namespace std;
ll dp[MAXN]={0};
int n=0,x=0;
int lose=0,win=0,use=0;
int main(){
	//freopen("test/P1802_10.in","r",stdin);
	cin>>n>>x;
	for(int i=1;i<=n;i++){
		cin>>lose>>win>>use;
		for(int j=x;j>=0;j--){
			if(j>=use){
				dp[j]=max(dp[j]+lose,dp[j-use]+win);
			}else{
				dp[j]+=lose;
			}
		}
	}
	
	cout<<(ll)(5*dp[x])<<endl;
	return 0;
}

(单击上方的 < 展开代码)

P1002 [NOIP2002 普及组] 过河卒

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<iostream>
#define ll long long
using namespace std;
const int dx[10]={0,1,2,2,1,-1,-2,-2,-1};
const int dy[10]={0,-2,-1,1,2,2,1,-1,-2};
int bx,by,mx,my;
ll map[25][25];
bool edge[25][25];
int main(){
	cin>>bx>>by>>mx>>my;
	bx+=2;
	by+=2;
	mx+=2;
	my+=2;
	map[2][1]=1;
	for(int i=0;i<10;i++){
		edge[mx+dx[i]][my+dy[i]]=1;
	}
	for(int i=2;i<=bx;i++){
		for(int j=2;j<=by;j++){
			if(edge[i][j]) continue;
			map[i][j]=map[i-1][j]+map[i][j-1];
		}
	}
	for(int i=0;i<=bx;i++){
		for(int j=0;j<=by;j++){
            /*
			cout<<map[i][j];
			if(edge[i][j]){
				cout<<"("<<edge[i][j]<<")";
			}else if(i==bx&&j==by){
				cout<<"(0)";
			}else{
				cout<<"   ";
			}
			cout<<" ";
            */
		}
		//cout<<endl;
	}
	cout<<map[bx][by]<<endl;
	return 0;
}

(单击上方的 < 展开代码)

洛谷题单 线性状态动态规划

P1020 [NOIP1999 普及组] 导弹拦截

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
#include<iostream>
#include<string.h>
using namespace std;
int a[500010];
int main(){
	int top=1;
	while(cin>>a[top++]);
	int dp[top+2];
	memset(dp,0,sizeof(dp));
	top-=2;
	int cnt=1;
	dp[1]=a[1];
    for(int i=2;i<=top;i++){
        if(dp[cnt]>=a[i]){
        	dp[++cnt]=a[i];
		}else{
			for(int j=1;1;j++){
                if(dp[j]<a[i]){
                    dp[j]=a[i];
                    break;
                }
            }
		}
    }
	cout<<cnt<<endl;
	cnt=1;
	dp[1]=a[1]; 
    for(int i=2;i<=top;i++){
        if(dp[cnt]<a[i]){
        	dp[++cnt]=a[i];
		}else{
			for(int j=1;1;j++){
                if(dp[j]>=a[i]){
                    dp[j]=a[i];
                    break;
                }
            }
		} 
    }
	cout<<cnt<<endl;
	return 0;
}

(单击上方的 < 展开代码)