hdu-6024

hdu-6024

struct node
{int x, c;bool operator<(const node &a) const{return x < a.x;}
};
// dp[i][0]为到第i个教室且第i个教室不建糖果店的花费前缀和，dp[i][1]为到第i个教室且第i个教室建糖果店的花费前缀和
int dp[N][2];
void solve()
{int n;while (cin >> n){vector<node> a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i].x >> a[i].c;dp[i][0] = dp[i][1] = INF;}sort(a.begin() + 1, a.end()); // 按坐标排序dp[1][1] = a[1].c;dp[1][0] = INF;for (int i = 2; i <= n; i++){int sum = 0;dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + a[i].c; // i教室建店此处一定花费a[i].c，所以再加上之前较优的花费for (int j = i - 1; j >= 1; j--){sum += (i - j) * (a[j + 1].x - a[j].x); // sum为从j+1教室到i教室的花费和dp[i][0] = min(dp[i][0], dp[j][1] + sum); // 判断j教室建店是不是最优}}cout << min(dp[n][0], dp[n][1]) << endl;}
}