Posted on 2007-08-06 12:00
oyjpart 阅读(1878)
评论(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
又是一个要求转化的题目
题目给了一个映射共点的条件 几乎没什么用
但是一旦你想到转化成这一点出发的一条线会与所有线相交
问题立刻转化成了枚举端点 确定这条线!