非官方题解 | B班Day07考试

༺དༀ༒PHKLSA༒ༀཌ༻

2026-08-18 16:23:32

发布于：浙江

17阅读

0回复

0点赞

此是非官方题解，请勿乱抄，你会被击败的

全是动态规划，最简单的还是1,5

正片开始

1：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1009],dp[1009];
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i){
	dp[i]=1;
	for(int j=1;j<i;++j){
		if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
	}
}
int ans=0;
for(int i=1;i<=n;++i){ans=max(ans,dp[i]);}
printf("%d",ans);
}

2：

#include<bits/stdc++.h> 
using namespace std;
int main(){
int n;
scanf("%d",&n);
int w[3][3];
for(int i=0;i<3;++i){
	for(int j=0;j<3;j++)scanf("%d",&w[i][j]);
}
long long dp[3]={0};
for(int i=0;i<n;++i){
	int a,b,c;scanf("%d %d %d",&a,&b,&c);
	if(i==0){
		dp[0]=a;
		dp[1]=b;
		dp[2]=c;
	}else{
		long long ndp[3];
		ndp[0]=max(dp[1]+w[1][0],dp[2]+w[2][0])+a;
		ndp[1]=max(dp[0]+w[0][1],dp[2]+w[2][1])+b;
		ndp[2]=max(dp[0]+w[0][2],dp[1]+w[1][2])+c;
		dp[0]=ndp[0];dp[1]=ndp[1];dp[2]=ndp[2];
	}
}
printf("%lld",max({dp[0],dp[1],dp[2]}));
return 0;
}

3：

#include<iostream>
using namespace std;
const long long MOD=998244353;
int main(){
int n,k;
scanf("%d %d",&n,&k);
long long dp0[2005],dp1[2005];
dp0[0]=1;dp1[1]=1;
for(int i=2;i<=n;++i){
	long long ndp0[2005]={0},ndp1[2005]={0};
	for(int j=0;j<=i;++j){
		ndp0[j]=(dp0[j]+dp1[j])%MOD;
		if(j>0)ndp1[j]=(dp0[j-1]+dp1[j])%MOD;
	}
	for(int j=0;j<=n;++j){dp0[j]=ndp0[j];dp1[j]=ndp1[j];}
}
printf("%lld",(dp0[k]+dp1[k])%MOD);
return 0;
}

4：

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
pair<int,int>a[100005];
for(int i=0;i<n;++i)scanf("%d %d",&a[i].first,&a[i].second);
sort(a,a+n);
int dp[100005],ans=0;
for(int i=0;i<n;++i){
	dp[i]=1;
	for(int j=0;j<i;j++){
		if(a[j].second<a[i].second){dp[i]=max(dp[i],dp[j]+1);}
	}
	ans=max(ans,dp[i]);
}
printf("%d",ans);
return 0;
}

5：

#include<bits/stdc++.h>
using namespace std;
string a,b;
int dp[1009][1009];
int main(){
	cin>>a>>b;
    int n=a.size(),m=b.size();
    a=' '+a;
    b=' '+b;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
            if(i+j<=1)continue;
			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])+(m-dp[n][m]));
    return 0;
}