題干：

總時(shí)間限制:?

1000ms

?

內(nèi)存限制:?

65536kB

描述

政府在某山區(qū)修建了一條道路，恰好穿越總共m個(gè)村莊的每個(gè)村莊一次，沒(méi)有回路或交叉，任意兩個(gè)村莊只能通過(guò)這條路來(lái)往。已知任意兩個(gè)相鄰的村莊之間的距離為di（為正整數(shù)），其中，0 < i < m。為了提高山區(qū)的文化素質(zhì)，政府又決定從m個(gè)村中選擇n個(gè)村建小學(xué)（設(shè) 0 < n < = m < 500 ）。請(qǐng)根據(jù)給定的m、n以及所有相鄰村莊的距離，選擇在哪些村莊建小學(xué)，才使得所有村到最近小學(xué)的距離總和最小，計(jì)算最小值。

輸入

第1行為m和n，其間用空格間隔
第2行為(m-1) 個(gè)整數(shù)，依次表示從一端到另一端的相鄰村莊的距離，整數(shù)之間以空格間隔。

例如
10 3
2 4 6 5 2 4 3 1 3
表示在10個(gè)村莊建3所學(xué)校。第1個(gè)村莊與第2個(gè)村莊距離為2，第2個(gè)村莊與第3個(gè)村莊距離為4，第3個(gè)村莊與第4個(gè)村莊距離為6，...，第9個(gè)村莊到第10個(gè)村莊的距離為3。

輸出

各村莊到最近學(xué)校的距離之和的最小值。

樣例輸入

10 2 3 1 3 1 1 1 1 1 3

樣例輸出

18

解題報(bào)告：

? ?dp[i][j]代表前i個(gè)村莊建立了j所小學(xué)的最小距離。

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個(gè)村中選擇n個(gè)村建小學(xué)（設(shè) 0 < n < = m < 500 ） int dis[555][555]; int f[555][555]; int dp[555][555];//dp[i][j] 代表前i個(gè)村莊創(chuàng)建n個(gè)j個(gè)學(xué)校的最小距離。 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;//其實(shí)這一句可以合并到下面，因?yàn)槟鉪is[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

簡(jiǎn)化一點(diǎn)的：

#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個(gè)村中選擇n個(gè)村建小學(xué)（設(shè) 0 < n < = m < 500 ） int sum[555]; int f[555][555]; int dp[555][555];//dp[i][j] 代表前i個(gè)村莊創(chuàng)建n個(gè)j個(gè)學(xué)校的最小距離。 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

或者分治：（但是這個(gè)耗時(shí)400ms？？上面那個(gè)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 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【OpenJudge - noi - 7624】山区建小学（dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。