HDU 6024(中国大学生程序设计竞赛女生专场1002)

时间:2023-12-14 13:24:20

这是CCPC女生专场的一道dp题。大佬们都说它简单,我并没有感到它有多简单。

先说一下题意:在一条直线上,有n个教室,现在我要在这些教室里从左到右地建设一些作为糖果屋,每个教室都有自己的坐标xi 和建造糖果屋的费用ci ,

如果在这里建造一个糖果屋,那么花费ci ,如果不建造糖果屋,则花费是当前教室的坐标与左边最靠近当前教室的糖果屋坐标之差,问最小花费。

一看这是个求最优解的问题,应该明白这是个dp问题,现在来考虑该问题状态的定义:

当我建设到第i个教室的时候,我有两种选择,建糖果屋或者不建糖果屋,影响我决策的是在左边离我最近的糖果屋的位置。并且我在建设前i个教室的时候,明显可以看出有i种相互独立的不同方案,即:

将离i最近的且在左边糖果屋建在  1号,2号,3号,......,k号,......,i号教室,所有的方案都可以分成这i类。我想知道建设前i个教室的最小费用,我只需挑出这i种方案中花费最小的那个就行。

并且,在我后面继续建设的时候,我一定还会用到这i种方案做基础,比如说我要建设第i+1个房间了,将最近的糖果屋建设在1~i已经有了现成的方案供我们选择,我们额外需要考虑的只是将糖果屋

建设在第i+1间教室时的情况。

于是我们定义状态dp[i][j]---->现在已经建设到第i个教室了,离i最近且在左边的的教室号为j时,我们能求得的最小花费。

状态转移方程:

if(i == j) dp[i][j] = minn[i - 1] + ci;

else dp[i][j] = dp[i - 1][j] + (xi - xj);

其中minn[k]指的是建设前k间教室的最小花费。

显然,当我们把最近的糖果屋建设在i号教室时,我们需要建设前i - 1间教室的最优解 + 建 i 号教室的费用,才能保证当前状态的最优解的生成。

这个minn[k]是可以顺带着算出来的,详见代码:

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 3005
#define F 0x7f
#define INF 0x3f3f3f3f3f3f3f
using namespace std;
struct room
{
long long x,c;
};
room store[maxn];
long long dp[][maxn];
long long minn[maxn];
const long long zero = ;
bool cmp(const room& a,const room& b)
{
return a.x < b.x;
}
int main()
{
int n;
while(scanf("%d",&n) == ){
for(int i = ;i <= n;++i) dp[][i] = INF;
for(int i = ;i <= n;++i) dp[][i] = ;
for(int i = ;i <= n;++i) minn[i] = INF;
for(int i = ;i <= n;++i) scanf("%lld%lld",&store[i].x,&store[i].c);
sort(store + ,store + n + ,cmp);
dp[][] = store[].c;
minn[] = dp[][];
for(int i = ;i <= n;++i){
for(int j = ;j <= i;++j){
if(i == j) dp[i & ][j] = minn[i - ] + store[i].c;
else dp[i & ][j] = dp[(i - ) & ][j] + (store[i].x - store[j].x);
minn[i] = min(minn[i],dp[i & ][j]);
}
}
printf("%lld\n",minn[n]);
}
return ;
}

这里有一个特别坑的地方:标号小的教室坐标未必小,即这些教室不一定是从左到右标号的。

同时为了减少内存开销,我采用了滚动数组。