题干：
总时间限制:
1000ms
内存限制:
65536kB
描述
政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
输入
第1行为m和n，其间用空格间隔
第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
例如
10 3
2 4 6 5 2 4 3 1 3
表示在10个村庄建3所学校。第1个村庄与第2个村庄距离为2，第2个村庄与第3个村庄距离为4，第3个村庄与第4个村庄距离为6，...，第9个村庄到第10个村庄的距离为3。
输出
各村庄到最近学校的距离之和的最小值。
样例输入
10 2
3 1 3 1 1 1 1 1 3 样例输出
18 解题报告：
dp[i][j]代表前i个村庄建立了j所小学的最小距离。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
//从m个村中选择n个村建小学（设 0 < n < = m < 500 ）
int dis[555][555];
int f[555][555];
int dp[555][555];//dp[i][j] 代表前i个村庄创建n个j个学校的最小距离。
int go(int i,int j) {
int mid = (i+j)>>1;
int res = 0;
for(; i<=j; i++) res += dis[i][mid];
return res;
}
int n,m;
int main() {
cin>>m>>n;
for(int i = 1; i<=m; i++) dis[i][i] = 0;
for(int x,i = 2; i<=m; i++) {
scanf("%d",&x);
dis[i-1][i] = dis[i][i-1] = x;//其实这一句可以合并到下面，因为你dis[i][i]=0了。。
for(int j = 1; j<i; j++) {
dis[j][i] = dis[j][i-1] + x;
dis[i][j] = dis[j][i];
}
}
for(int i = 1; i<=m; i++) {
for(int j = 1; j<=m; j++) {
f[i][j] = go(i,j);
}
}
memset(dp,INF,sizeof dp);
for(int i = 1; i<=m; i++) dp[i][1] = f[1][i];
for(int i = 2; i<=m; i++) {
for(int j = 2; j<=n; j++) {
if(j > i) continue;
for(int k = 1; k<i; k++) {
dp[i][j] = min(dp[i][j],dp[k][j-1] + f[k+1][i]);
}
}
}
printf("%d\n",dp[m][n]);
return 0 ;
}
//19:11 - 19:28 简化一点的：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
const int INF = 0x3f3f3f3f;
//从m个村中选择n个村建小学（设 0 < n < = m < 500 ）
int sum[555];
int f[555][555];
int dp[555][555];//dp[i][j] 代表前i个村庄创建n个j个学校的最小距离。
int go(int i,int j) {
int mid = (i+j)>>1;
int res = 0;
for(; i<=j; i++) res += abs(sum[mid]-sum[i]);
return res;
}
int n,m;
int main() {
cin>>m>>n;
for(int x,i = 2; i<=m; i++) {
scanf("%d",&x);
sum[i] = sum[i-1] + x;//边的前缀和
}
for(int i = 1; i<=m; i++) {
for(int j = 1; j<=m; j++) {
f[i][j] = go(i,j);
}
}
memset(dp,INF,sizeof dp);
for(int i = 1; i<=m; i++) dp[i][1] = f[1][i];
for(int i = 2; i<=m; i++) {
for(int j = 2; j<=n; j++) {
if(j > i) continue;
for(int k = j-1; k<i; k++) {
dp[i][j] = min(dp[i][j],dp[k][j-1] + f[k+1][i]);
}
}
}
printf("%d\n",dp[m][n]);
return 0 ;
}
//19:11 - 19:28 或者分治：（但是这个耗时400ms？？上面那个dp只有100多ms）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int MAX = 2e5 + 5;
const ll INF=1e15;
int a[MAX];
ll dp[MAX],ndp[MAX],s[MAX];
ll cal(int l,int r) {
return s[r]+s[l-1]-s[(l+r-1)/2]-s[(l+r)/2];
}
void solve(int l,int r,int p,int q) {
if(l>r)return;
int m=(l+r)>>1,x=p;
ndp[m]=INF;
for(int i = p; i<=q; i++) {
ll w=dp[i]+cal(i+1,m);
if(ndp[m]>w) {
ndp[m]=w;
x=i;
}
}
if(l<r) {
solve(l,m-1,p,x);
solve(m+1,r,x,q);
}
}
int main() {
int T,ca=0,k,i,j,m=0,K,n;
scanf("%d%d",&n,&K);
K = min(K,n);
a[1]=0;
for(int i = 2; i<=n; i++) {
int q;
scanf("%d",&q);
a[i] = a[i-1] + q;
}
sort(a+1,a+n+1);
for(int i = 1; i<=n; i++)s[i]=s[i-1]+a[i];
for(int i = 1; i<=n; i++) dp[i]=INF;
for(int i = 1; i<=K; i++) {
solve(1,n,0,n);
swap(dp,ndp);
}
printf("%lld\n",dp[n]);
return 0 ;
}
京公网安备 11010502036488号