?題意：n*n的矩陣，里面有m個(gè)格子是有任務(wù)要去完成的，t,x,y表示要在第t秒到達(dá)(x,y)的格子完成任務(wù)，問(wèn)你最多可以完成多少

解題思路：簡(jiǎn)單dp，將時(shí)間排個(gè)序后就是LIS
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;const int maxn = 10005; struct Node {int x,y,t;bool operator < (const Node a){return t < a.t;} }mission[maxn]; int n,m,dp[maxn];int main() {while(scanf("%d%d",&n,&m), m || n){for(int i = 1; i <= m; i++)scanf("%d%d%d",&mission[i].t,&mission[i].x,&mission[i].y);sort(mission+1,mission+1+m);dp[1] = 1;for(int i = 2; i <= m; i++){dp[i] = 1;for(int j = i - 1; j >= 1; j--){if((mission[i].t - mission[j].t) >= (abs(mission[i].x - mission[j].x) + abs(mission[i].y - mission[j].y)))dp[i] = max(dp[i],dp[j] + 1);}}int ans = 1;for(int i = 1; i <= m; i++)ans = max(ans,dp[i]);printf("%d\n",ans);}return 0; }

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的hdu 2881（简单dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。