Posted on 2007-08-06 12:00
oyjpart 閱讀(1891)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
PKU 3371 Stake Your Claim 這道題比較好的算法（而且我只能用這個(gè)過(guò)）就是把空缺的10個(gè)空位用3進(jìn)制狀態(tài)壓縮表示(0代表沒(méi)放，1代表0號(hào)選手放的，2代表1號(hào)選手放的） 然后做記憶化搜索
我開(kāi)始用的是AB剪枝 始終TLE 后來(lái)腦袋不清醒 在AB剪枝的同時(shí)加DP結(jié)果變成WA，后來(lái)想到AB剪枝的時(shí)候棋盤局面和剪枝有關(guān) 故不能隨便DP
不知哪位高人能給與指點(diǎn)解決這個(gè)問(wèn)題
下面是AB剪枝的大概流程，我們看到剪枝的時(shí)候返回值是跟sta（當(dāng)前子局面中最優(yōu)的）有關(guān)的，所以不能直接DP
1
2int search(int p, int sta) { //假定現(xiàn)在在計(jì)算S的子局面S2，sta則是S1的狀態(tài)值
3 if(p == 0) { //假定S局面取小，如果S2比S1大 則無(wú)用 即只要S2的子局面有一個(gè)比STA大 S2就無(wú)用了 退出
4 int now = -MAXINT; //S2局面取大 初始化為最小
5 for( every possible action ) {
6 //go this action;
7 int next = search(1, now);
8 now = Max(now, next);
9 //cancel this cation
10 if(now > sta) break; //S2的某個(gè)子局面出現(xiàn)了比sta還小的 退出
11 }
12 return now;
13 }
14 else { //假定S局面取大，如果S2比S1小 則無(wú)用 即只要S2的子局面有一個(gè)比STA小 S2就無(wú)用了 退出
15 int now = MAXINT;
16 for( every possible action ) {
17 //go this action;
18 int next = search(1, now);
19 now = Min(now, next);
20 //cancel this action
21 if(now < sta) break;
22 }
23 return now;
24 }
25}
26
TJU2879 Little Peter's Tower
題目給你一個(gè)范圍內(nèi)的積木 讓你隨即按次序得到T個(gè)積木 問(wèn)你怎么堆才能堆得最高
看到這題之后我一直以為題目要求我們找出一種最優(yōu)策略
但是苦于概率上的不確定性 沒(méi)有辦法找出
沒(méi)想到其實(shí)不是這樣的 其實(shí)這是一個(gè)DP task。我們能夠得知的策略就是如果我們只有一個(gè)積木 那么我們必然會(huì)堆一個(gè) 不管他有多高 那么如果我們定義這樣的狀態(tài)：
dp[top][time] 就可以得到下面的遞推式：
dp[top][time] = 平均(max(dp[top][time-1], dp[k][time-1] + k); //k是高度
于是程序?qū)懗鰜?lái)倒是很短
#include <iostream>
using namespace std;
double dp[120][120];
#define Max(a, b) ((a) > (b) ? (a) : (b))
int main() {
int R, H, T, i, j, k, r;
int ntc;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d %d %d", &R, &H, &T);
for(i = 1; i <= R; ++i) dp[0][i] = 0;
for(i = 1; i <= T; ++i) {
for(r = 1; r <= R; ++r) {
dp[i][r] = dp[i-1][r] * (R-r) * H;
for(j = 1; j <= r; ++j)
for(k = 1; k <= H; ++k)
dp[i][r] += Max(dp[i-1][r], dp[i-1][j] + k);
dp[i][r] /= R * H;
}
}
printf("%.6lf\n", dp[T][R]);
}
return 0;
}
TJU2868 Fire Balloon
一個(gè)很好的枚舉+DP的題目
其實(shí)題目很好轉(zhuǎn)化成二分圖 但是數(shù)據(jù)范圍限制讓我們不得不另尋他法
題目是一個(gè)有環(huán)圖,這個(gè)環(huán)在與:
1.上下兩個(gè)點(diǎn)之間存在連接
2.左右兩端連接起來(lái)了
于是我們才與枚舉狀態(tài) 消除后效性做DP!
首先把縱向的2個(gè)格子合并成一個(gè)大的狀態(tài) 這樣就退化成了一個(gè)環(huán)
然后再在任意兩點(diǎn)之間枚舉兩點(diǎn)之間的連接情況 這樣就退化成了一條鏈
終于可以開(kāi)始DP了 呵呵
PKU3265 Problem Solving
初看真的非常像貪心 結(jié)果是DP 隱藏的真好 推薦
TJU1037 Binary Search Tree I
這道題我居然不是觀察數(shù)據(jù) 猜測(cè) 然后證明
而是直接證明了才作。。。
做法：排序所有的數(shù)
如果一個(gè)數(shù)x的左邊那個(gè)數(shù)y和右邊的z那個(gè)數(shù)都比x先插入 那么它是葉子
如果都比x后插入 也是葉子
這樣證明：
二叉樹(shù)的一個(gè)重要性質(zhì)就是2分區(qū)間
比如插入一個(gè)8
就把分成了(-INF, 8] 和 [8, INF)
如果一個(gè)數(shù)x的左邊那個(gè)數(shù)和右邊那個(gè)數(shù)都比x先插入
那么他一定是葉子 為什么呢 如果他不是葉子
比如他有左子樹(shù) 那么y一定在他的左子樹(shù)里面
同理 可證明其他
PKU3304 Segments
又是一個(gè)要求轉(zhuǎn)化的題目
題目給了一個(gè)映射共點(diǎn)的條件 幾乎沒(méi)什么用
但是一旦你想到轉(zhuǎn)化成這一點(diǎn)出發(fā)的一條線會(huì)與所有線相交
問(wèn)題立刻轉(zhuǎn)化成了枚舉端點(diǎn) 確定這條線!