Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 终于枚举AC了

Posted by hanzeyao415 at 2015-11-01 00:41:11 on Problem 1944
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long LL;
int n,f[1010],s,r;
LL p,minn;
struct na
{
int m,n;
} e[10010];
int main()
{
minn=10000;
cin>>n>>p;
for(int i=1;i<=p;i++)
{

scanf("%d%d",&e[i].m,&e[i].n);
if(e[i].m==e[i].n)
{
i--;
p--;
}
if(e[i].m>e[i].n)
swap(e[i].m,e[i].n);
}
for(int k=1;k<=n;k++) // 断开[k,k+1];
{
int ans=0;
int pan=0;
r=0;
memset(f,0,sizeof(f));
for(int i=1;i<=p;i++)
{
if(e[i].m<=k&&e[i].n>=k+1)
{
f[1]=max(f[1],e[i].m);
f[e[i].n]=max(f[e[i].n],n+1);
}
else
f[e[i].m]=max(f[e[i].m],e[i].n);
}
for(int i=1;i<=n;i++)
{
if(f[i]==0) continue;
if(i>r){
ans+=f[i]-i;
r=f[i];
}
else if(f[i]>r)
{
ans+=f[i]-r;
r=f[i];
}
if(ans>minn)
break;
}
if(ans<minn)
minn=ans;
}
cout<<minn;
return 0;
}

/*
5 3
4 2
1 3
5 4
*/

Followed by: