又是输出路径。。。这题完全受上题影响，感觉两个题差不多。。用了基本上一样的算法写了，这题比较纠结，就是卡内存啊。。。5000*5000的数组开不了。。然后没办法，水了好几次MLE，看了一下虎哥的思路，完全不是一个套路，我写复杂了。。我啪啪按他的思路来了一次，就是过不了第三组，貌似得交了一二十次了。。。我把5000*5000降了降，因为只要i<=j的时候有用，乱搞了搞，2500*5000就过了。。。真心不容易啊。。。
只要把flag[i][j]记录 那一段，然后 pre记录i，sz记录上一次的结尾，写的很麻烦。。。O(N^2)的复杂度。
#include <cstring>
#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
#define INF 100000000
int flag[][];
int dp[];
int pre[];
int sz[];
struct node
{
int x,y;
int ax,ay;
}p[],s[];
bool cmp(node a,node b)
{
if(a.ax == b.ax)
return a.ay < b.ay;
else
return a.ax < b.ax;
}
int main()
{
int i,j,n,m,x,y,minz,key;
scanf("%d",&m);
for(n = ;; n ++)
{
scanf("%d%d",&x,&y);
if(x == &&y == )
break;
p[n].x = x;
p[n].y = y;
if(p[n].x < )
p[n].ax = ;
else
p[n].ax = p[n].x;
if(p[n].y > m)
p[n].ay = m;
else
p[n].ay = p[n].y;
if(p[n].ax > p[n].ay) continue;
if(p[n].ax > )
flag[-p[n].ax][-p[n].ay] = n+;
else
flag[p[n].ax][p[n].ay] = n+;
}
for(i = ; i <= m; i ++)
dp[i] = INF;
for(i = ;i <= m;i ++)
{
if(flag[][i])
{
pre[i] = ;
dp[i] = ;
}
}
for(i = ; i <= m; i ++)
{
minz = INF;
for(j = i - ; j >= ; j --)
{
if(minz > dp[j])
{
minz = dp[j];
key = j;
}
int ti,tj;
if(j > )
{
ti = - i;
tj = - j;
}
else
{
ti = i;
tj = j;
}
if(flag[tj][ti])
{
if(dp[i] > minz + )
{
pre[i] = j;
sz[i] = key;
dp[i] = minz + ;
}
}
}
}
if(dp[m] == INF)
printf("No solution\n");
else
{
printf("%d\n",dp[m]);
int num = ;
while(m)
{
int ti,tj;
if(pre[m] > )
{
ti = - pre[m];
tj = - m;
}
else
{
ti = pre[m];
tj = m;
}
s[num++] = p[flag[ti][tj] - ];
m = sz[m];
}
sort(s,s+num,cmp);
for(i = ; i < num; i ++)
printf("%d %d\n",s[i].x,s[i].y);
}
}