杭电1160解题报告
原题见这里
题目的大概意思：有一系列老鼠，每个老鼠有体重w以及奔跑的速度s，求这样一个最大的序列，使得
m[i+1].w > m[i].w && m[i+1].s < m[i].s
一开始，我用“DAG上的动态规划”来解决这道题目，把每一个老鼠看成是有向图中的一个顶点，有向边(v1, v2)存在的充要条件是m[v2].w > m[v1].w && m[v2].s < m[v1].s
那题目就转换为求一个DAG中不确定起点的最长路径，用记忆化搜索DP轻松KO，但是我就不知道为啥不能AC(算法复杂度太高？)，如果你知道，告诉我，不胜感激
d[i]表示以i为起点的最长路径
dp(i, n)//求解以i为起点的最长路径
最后，最长路径 = max {dp(i, n)}
#include <iostream>using namespace std;struct Mouse{ int w, s, id, next; Mouse(int _w, int _s): w(_w), s(_s), next(-1) {} Mouse(){}};Mouse m[1001];int dp[1001];int cmp(const void *a, const void *b) { if (((Mouse*)a)->w == ((Mouse*)b)->w) return ((Mouse*)b)->s - ((Mouse*)a)->s; else return ((Mouse*)a)->w - ((Mouse*)b)->w;}int main() { int w, s, n = 1; while (cin >> m[n].w >> m[n].s) m[n].id = n++; --n; qsort(m+1, n, sizeof(m[1]), cmp); int max = 0; int flag; for (int i = n; i >= 1; --i) { dp[i] = 1; for (int j = i + 1; j <= n; ++j) { if (m[j].w > m[i].w && m[j].s < m[i].s) if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; m[i].next = j; } } if (max < dp[i]) { max = dp[i]; flag = i; // dp[i]表示以i开头的最大长度 } } cout << max << endl; for (int i = 1; i <= max; ++i) { cout << m[flag].id << endl; flag = m[flag].next; } return 0;}注:鄙人最近按照杭电ACM分类来刷题，假期的最低限度是刷掉所有的DP类，并且每一道题目写一个解题报告，如果有志同道合的朋友，欢迎加QQ 823797837共同学习交流，也可以加群ACM新手群161986576，老鸟飞过