bzoj3892: [Usaco2014 Dec]Marathon
直接dp,f[i][j]表示当前在i,用了j次的最小值,转移很显然…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#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; } |