URAL 1303. Minimal Coverage(DP)

又是输出路径。。。这题完全受上题影响，感觉两个题差不多。。用了基本上一样的算法写了，这题比较纠结，就是卡内存啊。。。5000*5000的数组开不了。。然后没办法，水了好几次MLE，看了一下虎哥的思路，完全不是一个套路，我写复杂了。。我啪啪按他的思路来了一次，就是过不了第三组，貌似得交了一二十次了。。。我把5000*5000降了降，因为只要i<=j的时候有用，乱搞了搞，2500*5000就过了。。。真心不容易啊。。。

只要把flag[i][j]记录那一段，然后 pre记录i，sz记录上一次的结尾，写的很麻烦。。。O(N^2)的复杂度。

  1 #include <cstring>
  2 #include <cstdio>
  3 #include <string>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <map>
  8 using namespace std;
  9 #define INF 100000000
 10 int flag[2601][5111];
 11 int dp[5001];
 12 int pre[5001];
 13 int sz[5001];
 14 struct node
 15 {
 16     int x,y;
 17     int ax,ay;
 18 }p[99999],s[1001];
 19 bool cmp(node a,node b)
 20 {
 21     if(a.ax == b.ax)
 22         return a.ay < b.ay;
 23     else
 24         return a.ax < b.ax;
 25 }
 26 int main()
 27 {
 28     int i,j,n,m,x,y,minz,key;
 29     scanf("%d",&m);
 30     for(n = 0;; n ++)
 31     {
 32         scanf("%d%d",&x,&y);
 33         if(x == 0&&y == 0)
 34             break;
 35         p[n].x = x;
 36         p[n].y = y;
 37         if(p[n].x < 0)
 38             p[n].ax = 0;
 39         else
 40             p[n].ax = p[n].x;
 41         if(p[n].y > m)
 42             p[n].ay = m;
 43         else
 44             p[n].ay = p[n].y;
 45         if(p[n].ax > p[n].ay) continue;
 46         if(p[n].ax > 2500)
 47         flag[5010-p[n].ax][5010-p[n].ay] = n+1;
 48         else
 49         flag[p[n].ax][p[n].ay] = n+1;
 50     }
 51     for(i = 0; i <= m; i ++)
 52         dp[i] = INF;
 53     for(i = 0;i <= m;i ++)
 54     {
 55         if(flag[0][i])
 56         {
 57             pre[i] = 0;
 58             dp[i] = 1;
 59         }
 60     }
 61     for(i = 0; i <= m; i ++)
 62     {
 63         minz = INF;
 64         for(j = i - 1; j >= 0; j --)
 65         {
 66             if(minz > dp[j])
 67             {
 68                 minz = dp[j];
 69                 key = j;
 70             }
 71             int ti,tj;
 72             if(j > 2500)
 73             {
 74                 ti = 5010 - i;
 75                 tj = 5010 - j;
 76             }
 77             else
 78             {
 79                 ti = i;
 80                 tj = j;
 81             }
 82             if(flag[tj][ti])
 83             {
 84                 if(dp[i] > minz + 1)
 85                 {
 86                     pre[i] = j;
 87                     sz[i] = key;
 88                     dp[i] = minz + 1;
 89                 }
 90             }
 91         }
 92     }
 93     if(dp[m] == INF)
 94         printf("No solution
");
 95     else
 96     {
 97         printf("%d
",dp[m]);
 98         int num = 0;
 99         while(m)
100         {
101             int ti,tj;
102             if(pre[m] > 2500)
103             {
104                 ti = 5010 - pre[m];
105                 tj = 5010 - m;
106             }
107             else
108             {
109                 ti = pre[m];
110                 tj = m;
111             }
112             s[num++] = p[flag[ti][tj] - 1];
113             m = sz[m];
114         }
115         sort(s,s+num,cmp);
116         for(i = 0; i < num; i ++)
117             printf("%d %d
",s[i].x,s[i].y);
118     }
119 }