2017年8月15日（模拟7smoj2063,2064,2065暴力、动态规划、数学方法）

//暴力 
#include <stdio.h>
using namespace std;
#define maxN 50010
#define F(i,j,n)	for (int i=j; i<=n; i++)
int a[maxN],b[maxN];
int f[maxN*2];
int n;
int main()
{
	freopen("2063.in","r",stdin);
	freopen("2063.out","w",stdout);
	scanf("%d",&n);
	F(i,1,n)
	{
		int x;
		scanf("%d",&x);
		f[x]=1;	
	}
	int p1=0,p2=0;
	F(i,1,n*2)
	{
		if (f[i])	a[++p1]=i;
			else 	b[++p2]=i;
	}
	int j=1,ans=0;
	F(i,1,n)
		if (a[i]>b[j])
		{
			j++;
			ans++;
		}	
	printf("%d\n",ans);
	return 0;
}

//动态规划 
#include <stdio.h>
#include <algorithm>
using namespace std;
#define F(i,j,n)	for (int i=j; i<=n; i++)

int f[210][110][110];
int n,m,t,d;
int _abs(int x){	return x>0?x:-x;}
int main()
{
	freopen("2064.in","r",stdin);
	freopen("2064.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&t,&d);
	f[0][0][0]=1;
	F(i,1,t)
		F(j,0,n)
			F(k,0,m)
			if (f[i-1][j][k])
			{
				f[i][0][k]=1;
				f[i][j][0]=1;
				f[i][j][m]=1;
				f[i][n][k]=1;
				f[i][j][k]=1;
				int sum=j+k;
				if (sum>=n)	f[i][n][sum-n]=1;	else f[i][sum][0]=1;
				if (sum>=m) f[i][sum-m][m]=1;	else f[i][0][sum]=1;
			}
	int ans=d;
	F(i,0,n)
		F(j,0,m)
		if (f[t][i][j])
			ans=min(ans,_abs(i+j-d));
	printf("%d\n",ans);
	return 0;
}

//数学方法 
#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxN=50000;
struct Tnode{
	long long x,y;
}a[maxN+maxN];
long long c[maxN];

int cmp(Tnode x,Tnode y)
{
	return x.x<y.x;
}

int A,B,n,m;
int main()
{
	freopen("2065.in","r",stdin);
	freopen("2065.out","w",stdout);
	scanf("%d%d%d%d",&A,&B,&n,&m);
	int nn=0;
	for (int i=1; i<=n; i++)	scanf("%d",&c[i]);
	c[0]=0;		c[n+1]=B;
	sort(c,c+n+2);
	for (int i=1; i<=n+1; i++)
	{
		a[++nn].x=c[i]-c[i-1];
		a[nn].y=0;		
	}
	for (int i=1; i<=m; i++)	scanf("%d",&c[i]);
	c[0]=0;		c[m+1]=A;
	sort(c,c+m+2);
	for (int i=1; i<=m+1; i++)
	{
		a[++nn].x=c[i]-c[i-1];
		a[nn].y=1;
	}
	sort(a,a+nn+1,cmp);
	int h=n+1,l=m+1,h1=1,l1=1;
	long long ans=0;

	for (int i=1; i<=nn; i++)
	if (a[i].y==0)
	{
		ans+=(long long)a[i].x*m;
		a[i].y=-1;
		break;
	}
	for (int i=1; i<=nn; i++)
	if (a[i].y==1)
	{
		ans+=a[i].x*n;
		a[i].y=-1;
		break;
	}
	for (int i=1; i<=nn; i++)
	{
		if (a[i].y==0)	
		{
			ans+=(long long)a[i].x*(l-l1);
			h1++;
		}
		if (a[i].y==1)
		{
			ans+=(long long)a[i].x*(h-h1);
			l1++;
		}
	}
	printf("%lld\n",ans);
	return 0;
}