|
|
屬于狀態型的動態規劃，特難搞的那一類，狀態一多，轉換的時候難免遺漏一兩個。
這題還算，借助數據搞出來了，漏了兩個轉移，結果一組數據過不了。
后來加上就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;
}
|