【问题描述】

在一个数字序列，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。

【输入】

【输出】

【样例】

输入：8

           1 2 3 -1 -2 7 9 5

输出：5（长度）//1 2 3 7 9

 

#include <bits/stdc++.h>

using namespace std;

int a[1001];

int dp[1001];

int main(){

int v[]={0,8,10,6,3,7,2};//初始化物品价值数

int w[]={0,4,6,2,2,5,1};//初始化物品重量数

int n=6,c=12;//定义物品数量和被包容量

memset(f,0,sizeof(f));//初始化f数组为0

for(int i=1;i<=n;i++){//嵌套循环  行为物品

　　for(int j=1;j<=c;j++){//列为容量

　　　　if(j<w[i]){//背包装不下的情况（不拿的时候）

　　　　　　f[i][j]=f[i-1][j];//f值为上一个值

　　　　}else{//如果拿物品  利用状态转移方程

　　　　　　f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);

　　　　}

　　}

}

//打印输出f数组表的值

for(int i=1;i<=n;i++){

　　for(int j=1;j<=c;j++){

　　　　cout<<sewt(3)<<f[i][j];

　　　　}

　　　　cout<<endl;

}

return 0;

}