题目大意：一条直线上，有n个教室，现在我要在这些教室里从左到右地建设一些作为糖果屋，每个教室都有自己的坐标xi 和建造糖果屋的费用ci ，如果在这里建造一个糖果屋，那么花费ci ，如果不建造糖果屋，则花费是当前教室的坐标与左边最靠近当前教室的糖果屋坐标之差，问最小花费
dp的思路应该是很明显的
dp[i][1]代表第i个教室建立商店的最小花费，dp[i][0]代表第i个教室不建立商店的最小花费
dp[i][1] = min(dp[i - 1][0] , dp[i - 1][1]) + cost[i]
dp[i][0] = min(dp[j][1] + 距离代价）
其中距离代价是第 j + 1 个教室到第 i 个教室的所有点到第 j 个教室的距离之和
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node { ll x,y; }t[3010]; int n; ll dp[3010][2]; bool cmp(node k,node l) { return k.x < l.x; } int main() { while(~scanf("%d",&n)) { for(int i = 1;i <= n; ++i) scanf("%lld%lld",&t[i].x,&t[i].y); sort(t + 1,t + n + 1,cmp); dp[1][0] = dp[1][1] = t[1].y; for(int i = 2;i <= n; ++i) { dp[i][1] = min(dp[i - 1][0],dp[i - 1][1]) + t[i].y; dp[i][0] = dp[i - 1][1] + t[i].x - t[i - 1].x; ll sum = t[i].x - t[i - 1].x; ll k = 1; for(int j = i - 2;j >= 1; --j) { sum += (t[j + 1].x - t[j].x) * (++k); dp[i][0] = min(dp[i][0],dp[j][1] + sum); } } printf("%lld\n",min(dp[n][0],dp[n][1])); } return 0; }
