26年春季星光提高班第6课作业题解
2026-04-18 18:29:15
发布于：浙江
3阅读
0回复
0点赞
T1 ------必做题------
非正题，输出1即可
T2 最佳球队组建
可以针对其进行sort的排序，然后对其构成子序列，并求出其中值最大的。即可视年龄为序，求出不降序的最大子序列。若合法利用动态转移方程：dp[i]=max(dp[i],dp[j]+p[i].second);
样例代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int dp[n+1];
pair<int,int>p[n+1];
for(int i=1;i<=n;i++)cin>>p[i].second;
for(int i=1;i<=n;i++)cin>>p[i].first;
sort(p+1,p+n+1);
for(int i=1;i<=n;i++)
{
dp[i]=p[i].second;
for(int j=1;j<i;j++)
{
if(p[j].first==p[i].first)
{
dp[i]=max(dp[i],dp[j]+p[i].second);
}
else if(p[i].first<p[j].first&&p[i].second<=p[j].second)
{
dp[i]=max(dp[i],dp[j]+p[i].second);
}
else if(p[i].first>p[j].first&&p[i].second>=p[j].second)
{
dp[i]=max(dp[i],dp[j]+p[i].second);
}
}
}
int mx=1;
for(int i=1;i<=n;i++)
{
mx=max(mx,dp[i]);
}
cout<<mx;
return 0;
}
T3 信封问题
因为[1]只能装其他信封，被[1]装的只能去[1]信封或其他信封，则产生a[n-1]和a[n-2]种情况，而[1]能去产生这种情况n-1次所以得(a[i-1]+a[i-2])*(i-1)种。
样例代码
#include<bits/stdc++.h>
using namespace std;
long long a[27]={1,0};
int main()
{
int n;
cin>>n;
for(int i=2;i<=n;i++)a[i]=(a[i-1]+a[i-2])*(i-1);
cout<<a[n]<<"\n";
return 0;
}
T4 神秘的礼物
可以对信封进行 sort 排序，然后对其构成递增子序列，并求出其中长度最长的子序列。即宽度，高度同时满足递增要求，求出最长子序列。
样例代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int maxn=5010;
pair<pair<int,int>,int> a[maxn];
int n,w,h,dp[maxn],pre[maxn];
int dfs(int x)
{
if((dp[x]!=-1))return dp[x];
dp[x]=0;
for(int i=1;i<=n;i++)
{
if(a[i].first.first>a[x].first.first&&a[i].first.second>a[x].first.second&&dp[x]<dfs(i))
{
dp[x]=dp[i];
pre[x]=i;
}
}
dp[x]++;
return dp[x];
}
void wr(int x)
{
if(x)cout<<x<<" ";
if(pre[x])wr(pre[x]);
}
int main()
{
memset(dp,-1,sizeof(dp));
cin>>n>>w>>h;
a[0]=make_pair(make_pair(w,h),0);
for(int i=1;i<=n;i++)
{
a[i].second=i;
cin>>a[i].first.first>>a[i].first.second;
}
dfs(0);
cout<<dp[0]-1<<"\n";
if(dp[0])wr(0);
return 0;
}
T5 挖地雷
mp保存是否连接，再求出最大子序列，动态转移方程：dp[i]=max(dp[i],dp[j]+a[i]);
样例代码
#include <bits/stdc++.h>
using namespace std;
int dp[30],a[30];
int mp[30][30];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
{
cin>>mp[i][j];
}
}
int mx=-1;
for(int i=1;i<=n;i++)
{
dp[i]=a[i];
for(int j=1;j<i;j++)
{
if(mp[j][i])
{
dp[i]=max(dp[i],dp[j]+a[i]);
}
}
mx=max(mx,dp[i]);
}
cout<<mx<<"\n";
return 0;
}
T6 数字连线游戏
两行数字中，数值相等且位置顺序合法的数字进行配对，不相交则下标递增，实际就是求两行数字的最长公共子序列。动态转移方程：dp[i][j]=dp[i-1][j-1]+1;dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
样例代码
#include<iostream>
using namespace std;
int dp[2002][2002],a[1001],b[1001];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
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]);
}
}
}
cout<<dp[n][m]<<"\n";
return 0;
}
T7 ------选做题------
非正题，输出1即可
T8 古老卷轴的修复 （真是 普及-吗）
可以先求出两个字符串的最长公共子序列，再通过最长公共子序列得出最短公共超序列（直播说的是这个名吧？）。动态转移方程：dp[i][j]=dp[i-1][j-1]+1;max(dp[i-1][j],dp[i][j-1]);
样例代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
string s,t;
int dp[N][N];
int main()
{
cin>>s>>t;
s=" "+s;
t=" "+t;
for(int i=1;i<=s.size();i++)
{
for(int j=1;j<=t.size();j++)
{
if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
string ans="";
int i=s.size(),j=t.size();
while(i>0&&j>0)
{
if(s[i]==t[j])
{
ans+=s[i];
i--,j--;
}
else if(dp[i][j]==dp[i-1][j])
{
ans+=s[i];
i--;
}
else
{
ans+=t[j];
j--;
}
}
while(i>0) ans+=s[i--];
while(j>0) ans+=t[j--];
for(int k=ans.size()-1;k>=1;k--) if(ans[k]!=' ')cout<<ans[k];
return 0;
}
//aeebdab
//bccccdedbd
//bccccdaedebdab
T9 单词的最小修改
可以先求出两个字符串的最长公共子序列，输出剩下的字符数。动态转移方程：dp[i][j]=dp[i-1][j-1]+1;dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
T10 大师
这题不会！啊啊啊啊啊！我写的是题解里的代码：《26年春季星光提高班第5课讲义.pdf》。老师教一下。
原讲义代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=998244353;
const int N=20000;
ll dp[1007][2*N+7];
void add(ll& x,ll y)
{
x+=y;
if(x>=mod)x-=mod;
}
int main()
{
int n;
cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
int d=a[i]-a[j];
int idx=d+N;
add(dp[i][idx],dp[j][idx]);
add(dp[i][idx],1);
}
}
ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=2*N;j++)
{
add(ans,dp[i][j]);
}
}
ans=(ans+n)%mod;
cout<<ans<<"\n";
return 0;
}
这里空空如也
有帮助，赞一个