HDU 1160 FatMouse's Speed(DP)

本文主要是介绍HDU 1160 FatMouse's Speed(DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160

这个是一个很水的DP 了，复杂度O（n^2）的

首先先按照weight排序下，然后开始DP

dp方程很简单：dp[i]=MAX(dp[j]+1])           (j>0 && j<i && po[i].speed < po[j].speed && po[i].weight > po[j].weight)

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct point
{int weight;int speed;int num;
}po[1500];
int dp[1500];
int pos[1500];
int ans[1500];
int DP(int n)
{dp[0]=1;int i,j,k,num;for(i=1;i<n;i++){k=0,num=0;for(j=0;j<i;j++)if(po[i].speed < po[j].speed && po[i].weight > po[j].weight && dp[j]>k)k=dp[j],num=j;dp[i]=k+1;pos[i]=num;}num=0,k=0;for(i=0;i<n;i++)if(dp[i] > k)k=dp[i],num=i;printf("%d\n",k);k=0;while(pos[num]!=0){ans[k++]=po[num].num+1;num=pos[num];}ans[k]=po[num].num+1;for(i=k;i>=0;i--)printf("%d\n",ans[i]);return 0;
}
bool cmp(const point &a,const point &b)
{return a.weight < b.weight;
}
int main()
{int i,j;i=0;memset(pos,0,sizeof(pos));while(scanf("%d%d",&po[i].weight,&po[i].speed)!=EOF)po[i].num=i,i++;sort(po,po+i,cmp);//for(j=0;j<i;j++)//printf("%d\n",po[j].weight);DP(i);return 0;
}

这篇关于HDU 1160 FatMouse's Speed(DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---