HDU1160一点点技巧的DP 技巧|

仰天大笑出门去，我辈岂是蓬蒿人。这篇文章主要讲述HDU1160一点点技巧的DP相关的知识，希望能为你提供帮助。
1.??题目链接??。题目大意：给出一些老鼠的参数，每一行两个数据，第一个是老鼠的体重，第二个是速度，求出一组这样的老鼠，他们的体重在增加，但是速度在减小。尽可能是这个数量最多。输出这些老鼠的数量和对应的编号。
2.就是一个LIS问题，但是这里我们需要记录中间信息并且输出，我们在输入的时候给每一个老鼠就加上编号，然后按照体重排序DP即可，至于信息的记录，我们可以采用并查集中的pre[i]=j，这个数组的思想，pre[i]就是代表i的上一个数据是j，这样就一条链表一样完整的记录下了信息，其实在跑最短路的时候输出最短路的节点也是这样做的。代码奉上：

#include< bits/stdc++.h>
#include < iostream>
#include < algorithm>
using namespace std;
#pragma warning(disable:4996)
const int maxn = 1005;
struct node

intw, s, ind;
bool operator < (const node & n)const
if (w > = n.w)return true;
else if (w == n.w) return s< n.s;
else return false;

mice[maxn];

int dp[maxn];
int pre[maxn];
int main()

int w, s;
int ind = 0, pos = 0;
while (scanf("%d%d", & w, & s) != EOF)
mice[ind].w = w;
mice[ind].s = s;
mice[ind].ind = ind + 1;
ind++;

sort(mice, mice + ind);
for (int i = 0; i< ind; i++)dp[i] = 1;
memset(pre, -1, sizeof(pre));
for (int i = 0; i< ind; i++)
for (int j = 0; j< i; j++)
if (mice[j].w> mice[i].w& & mice[j].s< mice[i].s)
if (dp[i]< dp[j] + 1)
dp[i] = dp[j] + 1;
pre[i] = j;

int ans = -1;
for (int i = 0; i< ind; i++)
if (ans< dp[i])
ans = dp[i];
pos = i;

printf("%d\\n", dp[pos]);
while (pos != -1)
printf("%d\\n", mice[pos].ind);
pos = pre[pos];

return 0;