题目的意思就是给出你n个教室的位置和在这个教室建造糖果屋的价值,这个糖果屋的右边直到下一个糖果屋之前,所有没有建造糖果屋的教室与当前糖果屋的距离也要算在花费之类。也就是说,当前糖果屋的售卖范围要延伸到下一个右边的糖果屋。

所以当前糖果屋就有两种情况,建造或者不建造。

比赛的时候dp方程是写出来了,但是很尴尬,一直把上一个糖果屋选择为当前最小的那个糖果屋,没考虑到可能上一个糖果屋不建造会有更优的结果。

设dp[i]为在当前教室最优的情况。则有dp方程:

dp[i] = min(dp[i], dp[j]+ca[i].val-(n-i+1)*(ca[i].pos-ca[j].pos))


代码:

StatusAccepted
Time436ms
Memory1756kB
Length903
LangC++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <memory.h>
using namespace std;
#define MAX 0x3f3f3f3f
#define LL long long
const int inf= 0x3f3f3f3f;
const int maxn=3005;
struct Ca{
    int pos, val;
    bool operator<(const Ca &cmp) const{
        return pos<cmp.pos;
    }
}ca[maxn];
LL n, pd, dp[maxn], ans;
int main()
{
    while(~scanf("%d", &n)){
        pd=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d", &ca[i].pos, &ca[i].val);
        }
        sort(ca+1, ca+1+n);
        for(int i=2;i<=n;i++)pd+=ca[i].pos-ca[1].pos;
        memset(dp, MAX, sizeof(dp));
        dp[1]=ca[1].val+pd;
        ans=dp[1];
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=min(dp[i], dp[j]+ca[i].val-(n-i+1)*(ca[i].pos-ca[j].pos));
            }
            ans=min(ans, dp[i]);
        }
        printf("%lld\n", ans);
    }
    return 0;
}