|
|
属于状态型的动态规划，特难搞的那一类，状态一多，转换的时候难免遗漏一两个。
这题还算，借助数据搞出来了，漏了两个转移，结果一组数据过不了。
后来加上就AC了，时间还行，32MS。
思路：
从左往右开始放矩形，假设现在准备摆放第i列之后的矩形。
实际上我们只关注第i-1列是怎么摆的，前面怎么摆都无所谓。
所以，
第i列牛的状态 + 第i-1列摆放的状态 -> 第i列摆放的状态
摆放的状态有五种：
1. 光上面有
2. 光下面有
3. 上下都有但不属于同一个矩形
4. 空
5. 上下都有并且属于同一个矩形
牛的状态有四种，就是1~4。
然后就看怎么推了，详见代码。
代码中对状态的定义也是按照上面的顺序。
在网上找解题报告，发现有的大牛代码很短很快很牛逼！佩服！
ps：
一开始这份代码用g++和gcc提交是WA的，但c++提交可以AC。
我在本地测试了一下，发现g++和gcc编译后，数据是跑得过的。我的gcc版本很高，是4.3.3。
不知道是北大的网站有问题，还是我的代码有问题。不过后者可能性大很多。
后来，我把inline去掉（#define inline），再用g++、gcc提交，就过了！
很想不通，写其他代码的时候，也是gcc编译的，不都是这样写 inline 的吗，也没见出什么问题，也不可能出问题。
所以希望高手给指点一下！谢谢！
代码：
 #include <stdio.h>
#include <stdlib.h>
  enum  {
 UP, DOWN, UPDOWN, SPACE, CONN
 };
#define MAX_N 1024
#define MAX_AREA (15000000 * 2)
#define inline
struct cow_node {
int y, x;
};
int dp[2][5][MAX_N], (*cur)[MAX_N], (*pre)[MAX_N];
struct cow_node cows[MAX_N];
int N, K, B, max_k;
int cmp(const void *a, const void *b)
{
return ((struct cow_node *)a)->x - ((struct cow_node *)b)->x;
}
inline int min(int a, int b)
{
return a < b ? a : b;
}
inline void swap(void *a, void *b)
{
void *t = *(void **)a;
*(void **)a = *(void **)b;
*(void **)b = t;
}
inline void init(int (*t)[MAX_N])
{
int i;
for (i = 0; i <= max_k + 4; i++)
t[0][i] = t[1][i] = t[2][i] = t[3][i] = t[4][i] = MAX_AREA;
}
#if 0
inline void dump(int (*t)[MAX_N], int ptn)
{
#define dbp printf
int i, j;
  const char *strs[] = {
"up", "down", "updown", "space", "conn"
 };
const char *ptns[] = {
"*\n\n", "\n*\n", "*\n*\n", "\n\n"
};
dbp("---------\n%s", ptns[ptn]);
for (i = 0; i < 5; i++) {
dbp("%s: ", strs[i]);
for (j = 0; j <= max_k; j++)
dbp("%d->%d ", j, t[i][j]);
dbp("\n");
}
dbp("\n");
#undef dbp
}
#else
#define dump() {}
#endif
inline void calc(int ptn, int space_cnt)
{
int i;
#define UPDATE(_from, _to, _a_used, _k_used) \
cur[_to][i + _k_used] = min(cur[_to][i + _k_used], pre[_from][i] + _a_used)
#define CASE(_ptn, _code) \
if (ptn == _ptn) { \
for (i = 0; i <= max_k; i++) \
_code \
}
init(cur);
CASE(UP, {
UPDATE(UP, UP, 1, 0);
UPDATE(UPDOWN, UP, 1, 0);
UPDATE(UPDOWN, UPDOWN, 2, 0);
UPDATE(DOWN, UP, 1, 1);
UPDATE(DOWN, UPDOWN, 2, 1);
UPDATE(CONN, CONN, 2, 0);
UPDATE(CONN, UP, 1, 1);
UPDATE(SPACE, UP, 1, 1);
UPDATE(SPACE, CONN, 2, 1);
});
CASE(DOWN, {
UPDATE(DOWN, DOWN, 1, 0);
UPDATE(UPDOWN, DOWN, 1, 0);
UPDATE(UPDOWN, UPDOWN, 2, 0);
UPDATE(UP, DOWN, 1, 1);
UPDATE(UP, UPDOWN, 2, 1);
UPDATE(CONN, CONN, 2, 0);
UPDATE(CONN, DOWN, 1, 1);
UPDATE(SPACE, DOWN, 1, 1);
UPDATE(SPACE, CONN, 2, 1);
});
CASE(UPDOWN, {
UPDATE(UP, UPDOWN, 2, 1);
UPDATE(UPDOWN, UPDOWN, 2, 0);
UPDATE(DOWN, UPDOWN, 2, 1);
UPDATE(CONN, CONN, 2, 0);
UPDATE(SPACE, CONN, 2, 1);
UPDATE(SPACE, UPDOWN, 2, 2);
});
CASE(SPACE, {
UPDATE(UP, SPACE, 0, 0);
UPDATE(UP, UP, space_cnt, 0);
UPDATE(DOWN, SPACE, 0, 0);
UPDATE(DOWN, DOWN, space_cnt, 0);
UPDATE(UPDOWN, SPACE, 0, 0);
UPDATE(UPDOWN, UPDOWN, space_cnt*2, 0);
UPDATE(UPDOWN, UP, space_cnt, 0);
UPDATE(UPDOWN, DOWN, space_cnt, 0);
UPDATE(CONN, SPACE, 0, 0);
UPDATE(CONN, CONN, space_cnt*2, 0);
UPDATE(SPACE, SPACE, 0, 0);
});
#undef UPDATE
#undef CASE
dump(cur, ptn);
swap(&cur, &pre);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &N, &K, &B);
for (i = 0; i < N; i++)
scanf("%d%d", &cows[i].y, &cows[i].x);
qsort(cows, N, sizeof(cows[0]), cmp);
cur = dp[0];
pre = dp[1];
max_k = 2;
init(pre);
pre[SPACE][0] = 0;
for (i = 0; i < N; ) {
max_k = min(i + 2, K);
if (i && cows[i - 1].x + 1 != cows[i].x)
calc(SPACE, cows[i].x - cows[i - 1].x - 1);
if (i + 1 < N && cows[i + 1].x == cows[i].x) {
calc(UPDOWN, 0);
i += 2;
} else {
calc(cows[i].y == 1 ? UP : DOWN, 0);
i++;
}
}
calc(SPACE, 0);
printf("%d\n", pre[SPACE][K]);
return 0;
}
|