Codeforces 463 D.Gargari and Permutations【DP】
982 ワード
タイトルの大意:
1〜nのk個の配列(2<=k<=5)が与えられ、その中の最も長い共通のサブシーケンスが要求される.
作り方:
難しくないDPとして、dp[i]はiを最後とする最長の共通サブシーケンスの長さを表しています.各数は一つの配列に一回しか現れないので、私達は一つの二次元配列pos[i][j]で数字jが第i行でいくつかの位置に現れ、もう一つの配列cnt[i]でi]記録iが何回も現れました.i番目の数がk回発生した後に、この数で終了して共通のサブシーケンスを構成できると説明した場合、dp[i]=max(dp[j]+1)であり、i,jはpos[u]、[i]>pos[j](1=u<=k)を満足する.もちろん、時間を節約するために、以前計算したdp[i]値の下の表示をvectorに預けてもいいです.このvectorを通して条件に合う数を見つければいいです.
コード:
1〜nのk個の配列(2<=k<=5)が与えられ、その中の最も長い共通のサブシーケンスが要求される.
作り方:
難しくないDPとして、dp[i]はiを最後とする最長の共通サブシーケンスの長さを表しています.各数は一つの配列に一回しか現れないので、私達は一つの二次元配列pos[i][j]で数字jが第i行でいくつかの位置に現れ、もう一つの配列cnt[i]でi]記録iが何回も現れました.i番目の数がk回発生した後に、この数で終了して共通のサブシーケンスを構成できると説明した場合、dp[i]=max(dp[j]+1)であり、i,jはpos[u]、[i]>pos[j](1=u<=k)を満足する.もちろん、時間を節約するために、以前計算したdp[i]値の下の表示をvectorに預けてもいいです.このvectorを通して条件に合う数を見つければいいです.
コード:
#include
#include
#include
#include
#define N 1010
using namespace std;
int pos[6][N],cnt[N],a[6][N],dp[N];
vector q;
int main()
{
int n,k,ans=0;
scanf("%d%d",&n,&k);
for(int i=0;i