2009年09月30日 16:41 阅读(89) 评论(4) 分类：program 《usaco》

09.11.10
3.3.5 a game
经典博弈dp
以前在vijos看过没有仔细写

给一排数，两人轮流从头尾取数，一次只能取一个数
2个人都用最优策略，问2人最后最多各能取到的和

朴素的dp是用f1[i,j]表示先手的人从[i,j]处取到的最大值
f2[i,j]表示后手的人从[i,j]处取到的最大值

考虑先手
因为博弈是要让对手之后取到的情况最坏
所以对于f1[i,j]考虑f1[i+1,j]和f1[i,j-1]
选其中小的那个
所以就有下列dp式子
f1[i,j]:=─f2[i+1,j]+a[i]    (f1[i+1,j]
         └f2[i,j-1]+a[j]    (f1[i+1,j]>=f1[i,j-1])
初始值f1[i,i]:=a[i]  f2[i,i]:=0;
最后输出f1[1,n]  f2[1,n]

这样要多开一个二维数组
我们可以发现f1[i,j]+f2[i,j]=s[i,j]
所以可以将上式进行变形

f1[i,j]:=─f2[i+1,j]+a[i]=s[i+1,j]-f1[i+1,j]+a[i]=s[i,j]-f1[i+1,j]    (f1[i+1,j]
         └f2[i,j-1]+a[j]=s[i,j-1]-f1[i,j-1]+a[j]=s[i,j]-f1[i,j-1]    (f1[i+1,j]>=f1[i,j-1])
合并一下就变成
f1[i,j]:=max(s[i,j]-f1[i+1,j],s[i,j]-f1[i+1,j]);

这样省了空间，代码也简洁了，不过不直观
（好像我以前看过这个式子- -，没有看懂）

以上思想过程由若干篇题解辅助而成

----------------------------------------------------------------------

09.11.09

3.3.3 camelot

变态搜索猥琐截枝恶心细节

wocaonimei终于A掉了

我交了21遍啊日

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 1412 KB]
   Test 2: TEST OK [0.011 secs, 1412 KB]
   Test 3: TEST OK [0.011 secs, 1412 KB]
   Test 4: TEST OK [0.076 secs, 1412 KB]
   Test 5: TEST OK [0.335 secs, 1412 KB]
   Test 6: TEST OK [0.605 secs, 1412 KB]
   Test 7: TEST OK [0.011 secs, 1412 KB]
   Test 8: TEST OK [0.043 secs, 1412 KB]
   Test 9: TEST OK [0.205 secs, 1412 KB]
   Test 10: TEST OK [0.810 secs, 1412 KB]
   Test 11: TEST OK [0.022 secs, 1412 KB]
   Test 12: TEST OK [0.011 secs, 1412 KB]
   Test 13: TEST OK [0.022 secs, 1412 KB]
   Test 14: TEST OK [0.011 secs, 1412 KB]
   Test 15: TEST OK [0.011 secs, 1412 KB]
   Test 16: TEST OK [0.022 secs, 1412 KB]
   Test 17: TEST OK [0.000 secs, 1412 KB]
   Test 18: TEST OK [0.000 secs, 1412 KB]
   Test 19: TEST OK [0.043 secs, 1412 KB]

All tests OK.

Your program ('camelot') produced all correct answers!  This is your
submission #21 for this problem.  Congratulations!

我真tm大垃圾

----------------------------------------------------------------------

09.11.05

Section 3.1.4 Shaping Regions (rect1)

矩阵切割

今天终于耐下性子把这个东西搞掉了

其实不会很难

蛋定地在nocow把maigo的标程看一遍就明白了

原来一直蛋定不下来卡了很久

nocow是一个类似wiki的地方，全称是A Nest of Coding Wisdom 

里面专门是编程算法的资料，有usaco全题解，很牛逼

orz maigo大牛，把标程写得这么短小精悍效率巨高

在nocow看题解的时候发现了这个

这个真的是py贴上去的么= =

好骚啊好骚

以后写题要蛋定

蛋定啊蛋定

浮躁害死人

----------------------------------------------------------------------

09.10.22

3.1.5 Contact

这题是我见过的最恶心的输出格式。。

我交了8遍

----------------------------------------------------------------------

09.10.06

controlling companies

为了补偿玩了一下午植物大战僵尸的空虚我决定把这题日掉= =

题目翻译看这里

http://hi.baidu.com/lixiaotong90/blog/item/db49d7c4fad055af8226ac88.html

此题很畸形

写了很久

我写的算法是拿一个队列s放记录公司间的控制情况

s[p].x公司控制s[p].y公司

用boolean数组f[i,j]表示i是否控制j

刚开始的时候队列里面只有数据给的那些初始控制情况

每次枚举公司i

如果s[p].x公司不控制i公司就把s[p].y公司拥有i公司的股票加到s[p].x公司对i公司的股票里面

这时如果s[p].x可以控制i了就在队列里面加入s[p].x控制i这对关系并修改f

当时我只想到这里

然后交上去wa掉了最后一个点

后来自己想了一个数据

3

1 2 100

2 3 100

3 4 100

在做2 3的时候可以判断出2可以控制4

但是上面的算法没有判断出1也可以控制4

所以队列里面应该多加入一个1控制4的关系

也就是说要把s[fa[p]].x控制i的关系加入到队列里面去

fa[p]代表s[p]的父亲

然后就ac了

我是弱B

----------------------------------------------------------------------

09.10.05

2.3.2 nocows

此DP搞了1个多小时还是不会抄标程过了

一个树形dp

边界很ws

首先明确一下题目的意思：用N个点组成一棵深度为K的二叉树，求一共有几种方法？设dp[i,j]表示用i个点组成深度最多为j的二叉树的方法数，则：

dp[i,j]=∑(dp[k,j-1]×dp[i-1-k,j-1])(k∈{1..i-2})
边界条件：dp[1,i]=1
我们要求的是深度恰好为K的方法数S，易知S=dp[n,k]-dp[n,k-1]。但需要注意的是，如果每次都取模，最后可能会有dp[n,k]

----------------------------------------------------------------------

09.10.02

1.3.4 calfflac

找回文数

再一次被usaco严格的输出格式狠狠地操了

此题我交了7遍才A 

怎么可以出这么蛋疼的题啊日

----------------------------------------------------------------------

09.10.01

1.2.3 Name the Number

原来一个程序里面读2个文件要这样写的

var f:text;

 assign(input,'namenum.in');reset(input);
 readln(s1);
 close(input);
 assign(f,'dict.txt');reset(f);
 while not eof(f) do
   begin
    readln(f,s2);

 close(f);                   

    

----------------------------------------------------------------------

09.09.30
1.2.2 transform
变态模拟

被基础题狠狠地操了
被操得血肉模糊死无全尸。。。

干我程序实现能力怎么那么弱
我是水B我是大水B
干我怎么这么垃圾