poj 1160 Post Office(DP)

1237 단어
우선 하나의 정리를 알아야 한다. 한 구간에 우체국을 설치하려면 가장 좋은 위치는 반드시 가장 중간의 마을이고 마을 수가 짝수라면 중간의 두 점은 등가이다.
이것을 알면 한 구간에 우체국의 최소 거리와 거리를 설정할 수 있습니다.cost[i][j]는 구간 마을 i에서 마을 j까지 나타낸다.
dp[i][j]는 전 i개 마을에 j개 우체국을 설치한 후의 최소 거리와
그러면 이동은 dp[i][j]=min(dp[i-1][k]+cost[k+1][j])(매거k 및 k코드:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
int V,P;
int Abs(int n){
	return n>0?n:(-n);
}
int dp[40][305];
int p[305];
int cost[305][305];
int Get(int i,int j){
    int mid=(i+j)/2;
    int sum=0;

    for(int k=i;k<=j;k++){
		sum+=Abs(p[k]-p[mid]);
    }
    return sum;
}
int main(){

	while(~scanf("%d%d",&V,&P)){
		memset(dp,0x3f,sizeof(dp));
		for(int i=1;i<=V;i++){
			scanf("%d",&p[i]);
		}
		for(int i=1;i<=V;i++){
			for(int j=i;j<=V;j++){
				cost[i][j]=Get(i,j);
				//cout<<cost[i][j]<<endl;
			}
		}
		for(int i=1;i<=V;i++){
			dp[1][i]=cost[1][i];
		}
		for(int i=2;i<=P;i++){
			for(int j=i;j<=V;j++){
				for(int k=1;k<j;k++){
					dp[i][j]=min(dp[i][j],dp[i-1][k]+cost[k+1][j]);
				}
			}
		}
		cout<<dp[P][V]<<endl;
		
	}
	return 0;
}

좋은 웹페이지 즐겨찾기