HDU 5550dp + 접두어 및 최적화

제목:

한 빌딩에 n층이 있는데 층마다 두 종류의 사람이 있다. 하나는 좋아하는 공, 하나는 수영을 좋아한다. 지금 너는 층마다 구장을 개설하든지 수영장을 개설하든지 분배가 끝난 후에 공을 치는 사람은 구장에 가야 한다. 수영하는 사람은 수영장에 가야 한다. 가장 좋은 분배하에 모든 사람이 이동해야 하는 가장 짧은 거리와 얼마가 있느냐고 묻는다.

아이디어:

dp[i][0/1]는 i층이 0 또는 1로 배치되고 i+1층이 1 또는 0(i층과 반대)이라는 최소 대가를 나타낸다.dp[i][0]는 dp[j][1]에서 옮길 수 있는데 그 중에서 j가 i보다 작다. 그러면 우리는 j+1에서 i까지의 이 층을 0으로 건설하고 대가를 최소화하는 것을 고려한다. 그러면 이 층의 모든 1은 각각 양쪽으로 떠나야 한다.예를 들어 3, 4, 5, 6층, 3층과 4층의 1은 2층, 5층과 6층의 1은 7층으로 간다.이러한 상태 전이 방정식은 dp[i][0/1] = dp[j][1/0] + tmp이다.여기 tmp의 계산은 접두사와 최적화를 이용할 수 있다.전체 알고리즘의 복잡도를 O(n^2)로 한다.또한 경계 처리에 주의하여 구체적으로 코드를 보아야 한다.

코드:

#include 
using namespace std;
typedef long long ll;
const int MAXN = 4005;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll a[MAXN][2], dp[MAXN][2], sum[MAXN][2];

int main() {
    //freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
    int T, cs = 0;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &a[i][0], &a[i][1]);
            sum[i][0] = sum[i - 1][0] + a[i][0];
            sum[i][1] = sum[i - 1][1] + a[i][1];
        }
        ll ans = INF;
        for (int i = 1; i < n; i++) {
            for (int k = 0; k < 2; k++) {
                dp[i][k] = 0;
                for (int j = 1; j <= i; j++)
                    dp[i][k] += a[j][k ^ 1] * (i - j + 1);
                ll tmp = a[i][k ^ 1];
                if (i - 1 >= 1) dp[i][k] = min(dp[i][k], dp[i - 1][k ^ 1] + tmp);
                for (int j = i - 2; j >= 1; j--) {
                    int mid = (i - j + 1) / 2 + j;
                    tmp += sum[mid][k ^ 1] - sum[j][k ^ 1];
                    dp[i][k] = min(dp[i][k], dp[j][k ^ 1] + tmp);
                }
                ll tt = 0;
                for (int j = i + 1; j <= n; j++) tt += a[j][k] * (j - i);
                //cout << tt << endl;
                ans = min(ans, dp[i][k] + tt);
            }
        }
        printf("Case #%d: %lld
", ++cs, ans);
    }
    return 0;
}