AKSZ-DP2
2024-06-23 17:25:21
发布于:广东
AKSZ-DP
多维DP
如果低维无法表示状态,那就多开
题目:
好东西还要前缀法
好东西还要前缀法
蒙一个吧,我*我进AK班了!!!!!!!!
第一个是团队限定
#include<bits/stdc++.h>
using namespace std;
char X[1005],Y[1005];
int ans,dp[1005][1005];
// if(X[i]==Y[i]) dp[i][j]=dp[i-1][j-1]+1
// else dp[i][j]=max(dp[i-1][j],dp[i][j-1])
int main(){
scanf("%s\n%s",X+1,Y+1);
int lx=strlen(X+1),ly=strlen(Y+1); //长度
for(int i=1;i<=lx;i++){
for(int j=1;j<=ly;j++){
if(X[i]==Y[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[lx][ly];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=25;
int a[N],dp[N],c[N];
int m,n,ans,sum;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>m;
while(m--){
cin>>n;
sum=ans=0;
for(int i=1;i<=n;i++) cin>>a[i];
memset(dp,0,sizeof dp);
memset(c,0,sizeof c);
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);
}
ans=max(ans,dp[i]);
}
c[1]=1;
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++){
if(dp[j]+1==dp[i]&&a[j]<=a[i]) c[i]+=c[j];
}
if(c[i]==0) c[i]=1;
}
for(int i=1;i<=n;i++){
if(dp[i]==ans) sum+=c[i];
}
cout<<ans<<' '<<sum<<'\n';
}
return 0;
}
/*
3
5 9 9 9 8 9
4 9 8 7 6
5 1 2 1 8 0
*/
DAG模型,有向无环图
所有dp都可以转换成DAG模型。
模板
不想打了,递推都知道吧
今天做了一堆题脑子炸了,我**才很难
AC君!!!
你给我解释一下cin、cout比scanf、printf快?
这里空空如也
有帮助,赞一个