AtcoderDP专题

题目

A

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	scanf("%d", &n);
	int height[n + 1];
	int dp[n + 1];
	for(int i = 1; i <= n; i++){
		scanf("%d", &height[i]);
	}
	dp[1] = 0;
	dp[2] = abs(height[1] - height[2]);
	for(int i = 3; i <= n; i++){
		dp[i] = min(dp[i - 1] + abs(height[i - 1] - height[i]), dp[i - 2] + abs(height[i - 2] - height[i]));
	}
	printf("%d", dp[n]);
	return 0;
} 

B

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 100005;
int dp[MAXN], h[MAXN];
int main(){
	int n;
	int k;
	scanf("%d%d", &n, &k);
	memset(dp,0x3f,sizeof dp);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &h[i]);
	
	dp[1] = 0;
	for(int i = 2; i <= n; i++){
		for(int j = max(i - k, 1); j < i; j++){
			dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
		}
	}
	printf("%d", dp[n]);
	return 0;
}

C

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int A[MAXN], B[MAXN], C[MAXN];
int dp[MAXN][4];
int main(){
	int n;
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>A[i]>>B[i]>>C[i];
	}
	dp[1][1] = A[1];
	dp[1][2] = B[1];
	dp[1][3] = C[1];
	for(int i = 2; i <= n; i++){
		dp[i][1] += max(dp[i - 1][2], dp[i - 1][3]) + A[i];
		dp[i][2] += max(dp[i - 1][1], dp[i - 1][3]) + B[i];
		dp[i][3] += max(dp[i - 1][1], dp[i - 1][2]) + C[i];
	}
	int ans = max(dp[n][1], max(dp[n][2], dp[n][3]));
	printf("%d",ans);
	return 0; 
}

D

#include<bits/stdc++.h>
using namespace std;
const long long  MAXN = 1e5;
int w[MAXN];
long long v[MAXN];
long long dp[105][100005];
int N;
int W;
int main(){
	cin>>N>>W;
	for(int i = 1; i <= N; i++){
		cin>>w[i]>>v[i];
	}
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= W; j++){//容量 
			if(j < w[i]){//容量不够 
				dp[i][j] = dp[i - 1][j]; 
			}else{
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
			}
		}
	}
	cout<<dp[N][W]<<endl;
	return 0; 
} 

F

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3025;
char s[MAXN], t[MAXN], ans[MAXN];
int dp[MAXN][MAXN];
int main(){
	scanf("%s", s + 1);
	scanf("%s", t + 1);
	int n = strlen(s + 1);
	int m = strlen(t + 1);
	for(int i = n; i >= 1; i--){
		for(int j = m; j >= 1; j--){
			if(s[i] == t[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
			else dp[i][j] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	int l = 1, r = 1;
	while(l <= n && r <= m){
		if(s[l] == t[r]){
			printf("%c",s[l]);
			l++;
			r++;
		}else if(dp[l][r] == dp[l + 1][r]) l++;
		else r++;
	} 
	return 0;
}