【难题】动态规划 NOI 162:Post Office 7624:山区建小学——找状态方程有点难 思路详细

题目：点击打开链接

题目大意：V个村庄，P个邮局，邮局建在村庄上，求一种建法，让V个村庄到最近邮局的距离最小

dp[i][j]:表示在1~i个村庄中建j个邮局时的路径最小值 

m[i][j]:表示从i到j只建立一个邮局的路径的最小值

一开始我没懂，直到自己画了个图，假设把在5建的邮局移到4，则其他村庄的距离变化如图，从4到3不会变化，所以除法向下取整不会有问题。

则状态转移方程：m[i][j]=m[i][j-1]+a[i]-a[(i+j)/2]

dp[i][j]=min{dp[k][j-1]+m[k+1][i]}（1<=k<i）

思路参考了这位博主：点击打开链接

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int a[301],m[301][301]={0},dp[301][31]={0};
int main()
{int V,P,i,j,sum=0,k;cin>>V;cin>>P;for (i=1;i<=V;i++){cin>>a[i];sum+=a[i];}for (i=1;i<=V;i++)for (j=i+1;j<=V;j++)m[i][j]=m[i][j-1]+a[j]-a[(i+j)/2];//初始化dpfor (i=1;i<=V;i++)for (j=2;j<=P;j++)dp[i][j]=sum;for (i=1;i<=V;i++)dp[i][1]=m[1][i];//dpfor (i=1;i<=V;i++)for (j=2;j<=P;j++)for (k=j-1;k<i;k++)//因为1~k至少j-1个邮局，所以k>=j-1,k从j-1开始遍历dp[i][j]=min(dp[i][j],dp[k][j-1]+m[k+1][i]);cout<<dp[V][P];return 0;
}

7624:山区建小学 这道题思路类似，只需在输入时处理一下

a[i]为每一个山区的位置
mi[i][j],i到j之间建一个小学的路程

dp[i][j],1~i之间建了j个小学

注意：
1、不要忘记初始化：dp[i][1]=mi[1][i]
2、要保证状态转移方程中每一项都已算出来
     k>=j-1，k+1<=i，j-1>=1即j>=2

#include<iostream>
#include<string.h>
using namespace std;
int dp[501][501],a[501],mi[501][501];
int m,n;
int main()
{int i,j,x,k;cin>>m>>n;a[1]=0;for (i=2;i<=m;i++){cin>>x;a[i]=a[i-1]+x;}for (i=0;i<=m;i++)mi[i][i]=0;for (i=1;i<=m;i++)for (j=i+1;j<=m;j++)mi[i][j]=mi[i][j-1]+a[j]-a[(i+j)/2];for (i=1;i<=m;i++)for (j=1;j<=n;j++)dp[i][j]=250000;for (i=1;i<=m;i++)dp[i][1]=mi[1][i];for (i=2;i<=m;i++)for (j=2;j<=n;j++)for (k=j-1;k<i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+mi[k+1][i]);cout<<dp[m][n]<<endl;return 0;
}