最も長くて下がらないサブシーケンスの簡単な動態の計画の問題を求めます

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が存在する場合
    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<