动态规划（Week7）

T1 采药

太典了。

大家闭着眼睛都能敲出来。（？）

#include <iostream>
using namespace std;
int T,M;
int t[1005],v[1005],dp[1005];
int main(){
	cin>>T>>M;
	for(int i=1;i<=M;i++){
		cin>>t[i]>>v[i];
	}
	
	for(int i=1;i<=M;i++){
		for(int p=T;p>=1;p--){
			if(p>=t[i]){
				dp[p]=max(dp[p],dp[p-t[i]]+v[i]);
			}
		}
	}
	cout<<dp[T];
}

---

T2 最长上升子序列

题目：

逆向防御导弹？）

#include <iostream>
using namespace std;
const int N=1e6+5;
int n;
int num[5005];
int dp[5005];
int ans=1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		for(int j=i-1;j>=1;j--){
			if(num[j]<num[i]&&dp[i]<dp[j]+1){
				dp[i]=dp[j]+1;
			}
		}
		if(dp[i]==0)
		dp[i]=1;
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

---

T3 最大序列和

题目：

更新的式子同样很好找到。

要注意的只是判断的条件而已。

#include <iostream>
using namespace std;
int n,ans=-999999;
int num[200005],dp[200005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i];
		dp[i]=num[i];
		if(i!=1&&dp[i-1]>=0){
			dp[i]=dp[i]+dp[i-1];
		}
		if(dp[i]>ans) ans=dp[i];
	}
	cout<<ans;
	return 0;
}

---

T4 LCS

太典了，啧啧啧。

也是大家闭着眼睛也能敲出来的东西（？）

#include <bits/stdc++.h>
using namespace std;
int dp[3005][3005];
int max_,a1,b1;
string ans;
int main(){
	string a,b;
	getline(cin,a);
	getline(cin,b);
	int len1=a.length();
	int len2=b.length();
	//矩阵边边要从0开始，下标0为dp中的1.
	for(int i=0;i<len1;i++){
		for(int l=0;l<len2;l++){
			if(a[i]==b[l]) dp[i+1][l+1]=dp[i][l]+1;
			else dp[i+1][l+1]=max(dp[i][l+1],dp[i+1][l]);
			if(dp[i+1][l+1]>max_){
				max_=dp[i+1][l+1];
				a1=i+1;
				b1=l+1;
			}
		}	
	}
	while(a1>0&&b1>0){
		if(a[a1-1]==b[b1-1]){
			ans=a[a1-1]+ans;
			a1-=1;
			b1-=1;
		}
		else{
			if(dp[a1-1][b1]>dp[a1][b1-1])
			a1-=1;
			else
			b1-=1;
		}
	}
	cout<<ans;
}

---