首页 > 代码库 > dp求顺序hdu1160
dp求顺序hdu1160
题意是仅仅求一次的顺序。先依照速度从大到小排序,速度想等到按体重增序排列。
然后基本就变成了求已定顺序序列的最长递增序列递增,跟那个求一致最大序列和的基本一致。
dp【i】里存储的是到当前i最大的递增序列个数最大的数。
dp[i+1]就是在a【i+1】大于前面的a【j】的情况下,dp【i+1】=dp【j】+1;
输出的就是从最大的dp【】值从后往前输出,所以用了个栈改成从前往后。
以为题意仅仅输出一个正确序列就好。
思路是从開始的结构体排序。打一打就想出来的。bug,调了一天。确定dp【】最大值得时候和
须要记录角标。開始就弄混了,这个bug也是通过出数据找出来的。
第一次交没有输出序列个数,wa了2次。
ac代码:
#include<cstdio> #include<algorithm> #include<stack> using namespace std; stack<int > s; struct mice { int x,y,z; bool operator < (const mice&b ) const{ if(y==b.y) return x<b.x; return y>b.y; } }a[1010]; int dp[1010]; int main() { int i=0; while(scanf("%d%d",&a[i].x,&a[i].y)!=EOF) { a[i].z=i+1; i++; } // printf("\n"); // printf("i==%d\n",i); sort(a,a+i); // for(int j=0;j<i;j++) printf("%d %d %d\n",a[j].x,a[j].y,a[j].z); int maxx = 0,maxIndex=0; for(int j=0;j<i;j++) for(int k=0;k<j;k++){ if(a[k].x<a[j].x ) dp[j]=max(dp[k]+1,dp[j]); if(dp[j]>maxx) { maxx = dp[j]; maxIndex = j; } } // printf("maxx==%d\n",maxx); // for(int j=0;j<i;j++) printf("%d ",dp[j]); // printf("\n"); // printf("%d\n",a[maxx].z); // printf("%d\n",dp[maxx]+1); s.push(a[maxIndex].z); printf("%d\n",dp[maxIndex]+1); // printf("%d\n",a[maxIndex].z); dp[maxIndex]-=1; for(int k=maxIndex-1;k>=0;k--){ if(dp[k]==dp[maxIndex]){ // printf("%d\n",dp[k]); // printf("%d\n",a[k].z); s.push(a[k].z); dp[maxIndex]-=1; } } while(!s.empty()){ printf("%d\n",s.top()); s.pop(); } return 0; } /** 1 5 1 3 2 4 2 2 3 3 4 4 1 3 4 2 5 1 ^Z 1 5 1 2 4 3 4 4 6 1 3 2 1 3 7 3 3 5 2 2 4 4 2 8 5 1 9 0 1 2 0 0 2 1 3 4 4 5 3 1 */ /** 1 5 1 3 2 4 2 2 3 3 4 4 1 3 4 2 5 1 ^Z 1 5 1 2 4 2 3 3 3 4 2 4 5 1 5 0 1 2 3 4 5 1 2 3 4 5 */
dp求顺序hdu1160
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。