hdu1160简单dp最长下降子序列

/*
简单dp,要记录顺序
解:先排序,然后是一个最长下降子序列 ,中间需记录顺序
dp[i]=Max(dp[i],dp[j]+1);
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 1100
/*w,s代表重量和速度,index记录原来输入时的顺序下标,pre指向排序后的上一个下标,answer记录排序后每一个位置的最优值*/
typedef struct node {
int w,s,index,pre,answer;
}F;
F f[N];
int cmp(const void *a,const void *b) {
return (*(F *)a).w-(*(F *)b).w;
}
void print(int k) {
if(f[k].pre==-1) {
printf("%d\n",f[k].index);
return;
}
print(f[k].pre);
printf("%d\n",f[k].index);
}
int main() {
int n=0,w,s,i,j,k,index;
while(scanf("%d%d",&f[n].w,&f[n].s)!=EOF)
f[n].index=n+1,n++;
qsort(f,n,sizeof(f[0]),cmp);
for(i=0;i<n;i++) {
// printf("%d %d\n",f[i].w,f[i].s);
f[i].pre=-1;
f[i].answer=1;
for(j=0;j<i;j++)
if(f[i].w>f[j].w&&f[i].s<f[j].s&&f[i].answer<f[j].answer+1)
f[i].answer=f[j].answer+1,f[i].pre=j;
// printf("%d %d\n",f[i].answer,f[i].pre);
}
k=-1;
for(i=0;i<n;i++)
if(k<f[i].answer) {
k=f[i].answer;
index=//
}
printf("%d\n",k);//个数
print(index);//递归输出要求的数顺序
return 0;}
上一篇:《JS权威指南学习总结--7.8 数组方法》


下一篇:BZOJ4077 : [Wf2014]Messenger