bzoj3892: [Usaco2014 Dec]Marathon

12月25

bzoj3892: [Usaco2014 Dec]Marathon

直接dp，f[i][j]表示当前在i,用了j次的最小值，转移很显然…

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
	char ch=getchar();int f=0,x=1;
	while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}
	return f*x;
}
int f[505][505],x[505],y[505];
int main()
{
	int n=read(),k=read();
	for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();
	memset(f,0x3f3f3f3f,sizeof(f));
	f[1][0]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			for(int l=i-1;l;l--)
			{
				if(i-l-1>j) break;
				f[i][j]=min(f[i][j],f[l][j-(i-l-1)]+abs(x[i]-x[l])+abs(y[i]-y[l]));
			}
		}
	}
	int ans=2000000000;
	for(int j=0;j<=k;j++)
	{
		ans=min(ans,f[n][j]);
	}
	cout<<ans;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

char ch=getchar();int f=0,x=1;

while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}

return f*x;

}

int f[505][505],x[505],y[505];

int main()

{

int n=read(),k=read();

for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();

memset(f,0x3f3f3f3f,sizeof(f));

f[1][0]=0;

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

{

for(int j=0;j<=k;j++)

{

for(int l=i-1;l;l--)

{

if(i-l-1>j) break;

f[i][j]=min(f[i][j],f[l][j-(i-l-1)]+abs(x[i]-x[l])+abs(y[i]-y[l]));

}

int ans=2000000000;

for(int j=0;j<=k;j++)

{

ans=min(ans,f[n][j]);

}

cout<<ans;

}

mengbierr