[HDOJ1160]FatMouse's Speed（DP）

时间：2022-10-26 19:08:53

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160

FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

给一组w s，找出一个最长的序列，使得w是严格单调递增而且s是严格单调递减的。

两种做法，分别是关注w和关注s。

关注w：相当于是在s上求最长下降子序列。

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 typedef struct Node {

     int w;

     int s;

     int idx;

 }Node;

 const int maxn = ;

 Node mice[maxn];

 int n, ans;

 int dp[maxn];

 int pre[maxn];

 int st[maxn];

 int top;

 bool cmp(Node a, Node b) {

     if(a.w == b.w) return a.s > b.s;

     return a.w < b.w;

 }

 int main() {

     // freopen("in", "r", stdin);

     // freopen("out", "w", stdout);

     n = ;

     while(~scanf("%d %d", &mice[n].w, &mice[n].s)) {

         mice[n].idx = n;

         n++;

     }

     n--;

     sort(mice + , mice + n + , cmp);

     ans = ;

     int pos;

     memset(dp, , sizeof(dp));

     memset(pre, -, sizeof(pre));

     for(int i = ; i <= n; i++) {

         dp[i] = ;

         for(int j = ; j < i; j++) {

             if(dp[i] < dp[j] +  &&

                 mice[i].s < mice[j].s &&

                 mice[i].w > mice[j].w) {

                 dp[i] = dp[j] + ;

                 pre[mice[i].idx] = mice[j].idx;

             }

         }

         if(ans < dp[i]) {

             ans = dp[i];

             pos = mice[i].idx;

         }

     }

     top = ;

     for(int i = pos; ~i; i=pre[i]) st[top++] = i;

     printf("%d\n", ans);

     while(top) printf("%d\n", st[--top]);

     return ;

 }

关注s：相当于是在w上求最长上升子序列。

 #include <algorithm>

 #include <iostream>

 #include <iomanip>

 #include <cstring>

 #include <climits>

 #include <complex>

 #include <fstream>

 #include <cassert>

 #include <cstdio>

 #include <bitset>

 #include <vector>

 #include <deque>

 #include <queue>

 #include <stack>

 #include <ctime>

 #include <set>

 #include <map>

 #include <cmath>

 using namespace std;

 typedef struct Node {

     int w;

     int s;

     int idx;

 }Node;

 const int maxn = ;

 Node mice[maxn];

 int n, ans;

 int dp[maxn];

 int pre[maxn];

 int st[maxn];

 int top;

 bool cmp(Node a, Node b) {

     if(a.s == b.s) return a.w < b.w;

     return a.s > b.s;

 }

 int main() {

     // freopen("in", "r", stdin);

     // freopen("out", "w", stdout);

     n = ;

     while(~scanf("%d %d", &mice[n].w, &mice[n].s)) {

         mice[n].idx = n;

         n++;

     }

     n--;

     sort(mice + , mice + n + , cmp);

     ans = ;

     int pos;

     memset(dp, , sizeof(dp));

     memset(pre, -, sizeof(pre));

     for(int i = ; i <= n; i++) {

         dp[i] = ;

         for(int j = ; j < i; j++) {

             if(dp[i] < dp[j] +  &&

                mice[i].w > mice[j].w) {

                 dp[i] = dp[j] + ;

                 pre[mice[i].idx] = mice[j].idx;

             }

         }

         if(ans < dp[i]) {

             ans = dp[i];

             pos = mice[i].idx;

         }

     }

     top = ;

     for(int i = pos; ~i; i=pre[i]) st[top++] = i;

     printf("%d\n", ans);

     while(top) printf("%d\n", st[--top]);

     return ;

 }

注意小心关注w时s相等的情况和关注s时w相等的情况。不知道为什么，关注w时没有注意s相等的代码可以AC但是关注s的时候必须要注意w相等要continue掉。应该是数据水了吧。

相关文章