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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
|
#include<ctime> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<set> #include<queue> #include<deque> #include<stack> #include<bitset> #include<vector> #include<algorithm> #include<iostream> using namespace std; #ifdef DEBUG const int LOCAL=1; #else const int LOCAL=0; #endif
namespace mine { typedef long long ll; const int INF=0x3f3f3f3f;
const int MAX_N=310; ll f[MAX_N][40],fm[MAX_N][40]; ll a[MAX_N],w[MAX_N][MAX_N]; void () { int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int l=1;l<=n;l++) for(int r=l;r<=n;r++) w[l][r]=w[l][r-1]+a[r]-a[(l+r)/2];
memset(f,63,sizeof f);f[0][0]=0; for(int k=1;k<=m;k++) { for(int i=n;i>=k;i--) { int fl=fm[i][k-1],fr=(i==n)?n:fm[i+1][k]; for(int j=fl;j<=fr and j<i;j++) { ll now=f[j][k-1]+w[j+1][i]; if(now<f[i][k]) f[i][k]=now,fm[i][k]=j; } } } printf("%lld",f[n][m]); } }; int () { mine::main(); }
|
近期评论