最も長くて下がらないサブシーケンスの簡単な動態の計画の問題を求めます
1196 ワード
テーマは最も長くて下がらない子の序列を求めます
記述には、n(1≦n≦200)個の異なる整数からなる数列が設けられ、b(1)、b(2)、...、b(n)b(1)、b(2)、...、b(n)、b(i)≠b(j)(i≠j)b(i)≠b(j)(i)≠b(j)(i)≠b(i)≠j)と記載され、i 1が存在する場合
フォーマットの第1の動作nを入力し、第2の動作をスペースで区切ったn個の整数を入力します.
出力フォーマットの第1の動作は最大個数maxを出力する(形式はサンプルを参照).第2の行為max個の整数が形成した下がらないシーケンスで、この問題はシーケンスが唯一であることを保証する.
入力サンプル14 13 7 9 16 38 24 37 18 44 19 21 22 63 15
出力サンプルmax=8 7 9 16 18 19 21 22 63
テーマ構想の簡単な動的計画は,状態遷移方程式を簡単に打ち出し,dp配列を再利用すればよい.
記述には、n(1≦n≦200)個の異なる整数からなる数列が設けられ、b(1)、b(2)、...、b(n)b(1)、b(2)、...、b(n)、b(i)≠b(j)(i≠j)b(i)≠b(j)(i)≠b(j)(i)≠b(i)≠j)と記載され、i 1が存在する場合
13,7,9,16,38,24,37,18,44,19,21,22,63,15。
13,16,18,19,21,22,63 7 ,
7 ,9,16,18,19,21,22,63 8 。
フォーマットの第1の動作nを入力し、第2の動作をスペースで区切ったn個の整数を入力します.
出力フォーマットの第1の動作は最大個数maxを出力する(形式はサンプルを参照).第2の行為max個の整数が形成した下がらないシーケンスで、この問題はシーケンスが唯一であることを保証する.
入力サンプル14 13 7 9 16 38 24 37 18 44 19 21 22 63 15
出力サンプルmax=8 7 9 16 18 19 21 22 63
テーマ構想の簡単な動的計画は,状態遷移方程式を簡単に打ち出し,dp配列を再利用すればよい.
#include
#include
using namespace std;
int ans[200];int Max=0,Max_f;int n,a[1000]={},dp[1000]={},tot=0;
void findans(int Max_f){
//cout<>n; //
for(int i=0;i>a[i]; dp[i]=1;
}
for(int i=1;idp[i])
ans[i]=j; //
dp[i]=max(dp[j]+1,dp[i]); //
}
}
for(int i=0;iMax){
Max=dp[i];
Max_f=i;
}
} // Max Max
cout<