杭电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，老鸟飞过