poj1160-Post Office

[이것은 DP 문제입니다.]
dp[i][j]는 i개 마을이 j개 우체국을 공유하는 가장 좋은 거리의 총계를 나타낸다.

dp[i][j] = min(dp[i][j], dp[k][j-1] + sum[k][i]);

마을 i를 나타내는 좌표

sum[i][j] =  sum[i][j-1] + p[j] - p[(i+j)/2];

AC 코드:

#include
#include
#include
using namespace std;
#define min(a, b) (a) < (b) ? (a) : (b)
int dp[310][31];
int sum[310][310];
int v, p;
int pos[310];
int main(){
    while(scanf("%d%d", &v, &p) != EOF){
        for(int i = 1; i <= v; i++){
            cin>>pos[i];
        }
        memset(sum, 0, sizeof(sum));
        for(int i = 1; i < v; i++){
            for(int j = i + 1; j <= v; j++){
                sum[i][j] = sum [i][j-1] + pos[j] - pos[(i+j)/2];
            }
        }
        for(int i = 1; i <= v; i++){
            dp[i][i] = 0;
            dp[i][1] = sum[1][i];
        }
        for(int j = 2; j <= p; j++){
            for(int i = j+1; i <= v; i++){
                dp[i][j]=100000;
                for(int k = j - 1; k < i; k++){
                    dp[i][j] = min(dp[i][j], dp[k][j-1] + sum[k+1][i]);
                }

            }
        }
        printf("%d
", dp[v][p]);
    }
    return 0;
}