一道基础性的动态规划题目,拿来练手,求最长不上升子序列和不上升子序列的最小划分数
代码有问题,测试数据:6,5,1,7,3,2
第一次动规的时候太贪了,6,5,3,2,导致第二问无法取得最优解,还要研究研究,不过过vijos的数据是没问题的。
#include#include #include using namespace std;int a[30];int f[30];int last[30];int vis[30];int n,end,total;int ans=0;void input(){ int i=0; while(cin>>a[i]) { getchar(); i++; } n=i; end=n-1; total=n;}void work(){ memset(last,-1,sizeof(last)); for(int i=0;i =max && vis[i]!=1)//!!!!!!! >= > { //cout<<"max="< <<" f["< <<"]="< <