河北省建设厅官方网站 官网,建设银行 网站 字体,付费腾讯企业邮箱入口,淘客网站推广免备案很好玩的一道类似LCS的DP 问题 定义dp(i) 为考虑最后一个字符串#xff0c;且选择a#xff08;i#xff09;得到的最大LIS值
然后枚举所有小于i的位置#xff0c;可以更新的条件是 所有的字符串中都有a[j]a[i] 这个用map一处理就好了 #includebits/stdc.h
usi… 很好玩的一道类似LCS的DP 问题 定义dp(i) 为考虑最后一个字符串且选择ai得到的最大LIS值
然后枚举所有小于i的位置可以更新的条件是 所有的字符串中都有a[j]a[i] 这个用map一处理就好了 #includebits/stdc.h
using namespace std;
using ll long long;
const int N 3e510;int n,m;
mapint,intmp[10];
int a[N];
int dp[N];
void solve()
{ cinnm;for(int i1;im-1;i)for(int j1;jn;j){int x;cinx;mp[i][x] j;}for(int i1;in;i)cina[i];for(int i1;in;i)dp[i] 1;int ans 1;for(int i1;in;i){for(int j1;ji;j){bool st true;for(int k1;km-1;k)//mp[k][a[j]]mp[k][a[i]]if(mp[k][a[j]]mp[k][a[i]])st false; if(st)dp[i] max(dp[i],dp[j]1);} ans max(ans,dp[i]);}//for(int i1;in;i)coutdp[i] \n[in];coutans\n;}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int _;_ 1;while(_--)solve();
}
