Posted on 2007-08-06 12:00
oyjpart 閱讀(1906)
評論(2) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
PKU 3371 Stake Your Claim 這道題比較好的算法（而且我只能用這個過）就是把空缺的10個空位用3進制狀態壓縮表示(0代表沒放，1代表0號選手放的，2代表1號選手放的） 然后做記憶化搜索
我開始用的是AB剪枝 始終TLE 后來腦袋不清醒 在AB剪枝的同時加DP結果變成WA，后來想到AB剪枝的時候棋盤局面和剪枝有關 故不能隨便DP
不知哪位高人能給與指點解決這個問題
下面是AB剪枝的大概流程，我們看到剪枝的時候返回值是跟sta（當前子局面中最優的）有關的，所以不能直接DP
1
2int search(int p, int sta) { //假定現在在計算S的子局面S2，sta則是S1的狀態值
3 if(p == 0) { //假定S局面取小，如果S2比S1大 則無用 即只要S2的子局面有一個比STA大 S2就無用了 退出
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的某個子局面出現了比sta還小的 退出
11 }
12 return now;
13 }
14 else { //假定S局面取大，如果S2比S1小 則無用 即只要S2的子局面有一個比STA小 S2就無用了 退出
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
題目給你一個范圍內的積木 讓你隨即按次序得到T個積木 問你怎么堆才能堆得最高
看到這題之后我一直以為題目要求我們找出一種最優策略
但是苦于概率上的不確定性 沒有辦法找出
沒想到其實不是這樣的 其實這是一個DP task。我們能夠得知的策略就是如果我們只有一個積木 那么我們必然會堆一個 不管他有多高 那么如果我們定義這樣的狀態：
dp[top][time] 就可以得到下面的遞推式：
dp[top][time] = 平均(max(dp[top][time-1], dp[k][time-1] + k); //k是高度
于是程序寫出來倒是很短
#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
一個很好的枚舉+DP的題目
其實題目很好轉化成二分圖 但是數據范圍限制讓我們不得不另尋他法
題目是一個有環圖,這個環在與:
1.上下兩個點之間存在連接
2.左右兩端連接起來了
于是我們才與枚舉狀態 消除后效性做DP!
首先把縱向的2個格子合并成一個大的狀態 這樣就退化成了一個環
然后再在任意兩點之間枚舉兩點之間的連接情況 這樣就退化成了一條鏈
終于可以開始DP了 呵呵
PKU3265 Problem Solving
初看真的非常像貪心 結果是DP 隱藏的真好 推薦
TJU1037 Binary Search Tree I
這道題我居然不是觀察數據 猜測 然后證明
而是直接證明了才作。。。
做法：排序所有的數
如果一個數x的左邊那個數y和右邊的z那個數都比x先插入 那么它是葉子
如果都比x后插入 也是葉子
這樣證明：
二叉樹的一個重要性質就是2分區間
比如插入一個8
就把分成了(-INF, 8] 和 [8, INF)
如果一個數x的左邊那個數和右邊那個數都比x先插入
那么他一定是葉子 為什么呢 如果他不是葉子
比如他有左子樹 那么y一定在他的左子樹里面
同理 可證明其他
PKU3304 Segments
又是一個要求轉化的題目
題目給了一個映射共點的條件 幾乎沒什么用
但是一旦你想到轉化成這一點出發的一條線會與所有線相交
問題立刻轉化成了枚舉端點 確定這條線!