[cpp]?
/**
*?? Author : johnsondu
*?? time : 2013-4-7
*?? Type: DP, I want to really understand it
*?? problem: FatMouse's Speed
*?? url:
http://acm.hdu.edu.cn/showproblem.php?pid=1160
*/?
?
#include ??
#include ??
#include ??
#include ??
#include ??
#include ??
using namespace std ;?
?
#define max(a, b) (a > b ? a : b)??
struct Node?
{?
??? int w, s ;?
??? int idx ;?
}node[1005] ;?
int n, dp[1005] ;?
?
bool cmp (const Node &a, const Node &b)?
{?
??? if (a.w != b.w)?
??????? return a.w < b.w ;?
??? return a.s > b.s ;?
}?
?
int main ()?
{?
??? int i, j ;?
??? //freopen ("data.txt", "r", stdin) ;??
??? n = 0 ;?
??? while (scanf ("%d%d", &node[n].w, &node[n].s) != EOF)?
??? {?
??????? node[n].idx = n ;?
??????? n ++ ;?
??? }?
??? sort (node, node + n, cmp) ;?
?
??? for (i = 0; i < n; i ++)?
??????? dp[i] = 1 ;?
?
??? int num = 0 ;?
??? for (i = 0; i < n-1; i ++)?
??? {?
??????? for (j = i+1; j < n; j ++)?
??????????? if (node[j].w > node[i].w && node[j].s < node[i].s)?
??????????? {?
??????????????? dp[j] = max(dp[i]+1, dp[j]) ;?????????? //状态转移方程??
??????????????? if (dp[j] > dp[num])?
??????????????????? num = j ;?????????????????????????? //记录最大值下标??
??????????? }?
??? }?
??? printf ("%d\n", dp[num]) ;?
??? int tp = num ;?
??? vector mm ;?
??? mm.push_back(num) ;?
??? for (i = num-1; i >= 0; i --)?? //寻找路径??
??????? if (dp[num] == dp[i] + 1)?
??????? {?
??????????? mm.push_back(i) ;?
??????????? num = i ;?
??????? }?
??? for (i = dp[tp]-1; i >= 0; i --)?
??????? printf ("%d\n", node[mm[i]].idx+1) ;?
?
??? return 0 ;?
}?
|