Skip to content

计划7.11-7.20

以学习为主。知道自己来这里干嘛的。

上午仔细做题,注意时间分配,练Emacs,练GDB。

中午另安排。

下午要把上午的所有题都搞清楚,除非公认不可能搞清楚。

晚上总结一天。

注意珍惜时间。

根据明天的情况再细化。

One Comment

  1. Orztianyi wrote:

    这题是我比较得意的一道题目,需要一定的思考强度,算法的主要部分是DP。
    首先,容易证明,红法师一定排在最后。(提示:只需证明,将RG或RB交换成GR或BR一定更优。)所以,若使用r个红法师,只须确定其余N-r个排在前面的蓝、绿法师如何摆放,这一步可以使用DP来解决。
    设f[g][b]表示使用g个绿法师、b个蓝法师可造成的最大伤害,求解f[g][b]只须枚举最后一格放的是何种法师,可以由f[g-1][b]和f[g][b-1]递推得到,具体的DP方程无须给出。
    对于每个f[g][b],加上最后的N-g-b个红法师带来的伤害,以及在红法师的区域由于中毒带来的伤害(后者易忽视),找到最优值即可。算法的复杂度是O(N^2)。
    由于结果较大,需要使用64位整数,本来打算出成像NOIP2007的第三题一样需要用高精,不过为了控制难度,最终没有这样做。
    数据范围中的0<=Tb then exit(a) else exit(b);
    end;
    begin
    assign(input,’mtower.in’);reset(input);
    assign(output,’mtower.out’);rewrite(output);
    readln(n,r,g,b,t);
    f[0,0]:=r*n*t;
    ans:=f[0,0];
    for i:=0 to n do
    for j:=0 to n do
    if (i+j<=n)and((i0)or(j0)) then
    begin
    x1:=0;x2:=0;
    if i-1>=0 then x1:=f[i-1,j]+(n-i-j)*(t+b*j)*g-r*(t+j*b);
    if j-1>=0 then x2:=f[i,j-1]+(n-i-j)*(r+i*g)*b-r*(t+(j-1)*b);
    f[i,j]:=max(x1,x2);
    if f[i,j]>ans then ans:=f[i,j];
    end;
    writeln(ans);
    close(input);close(output);
    end.
    但我觉得f[i,j]:=max(f[i-1,j]+(n-i-j)*(t+b*j)g-r(t+j*b),
    f[i,j-1]+(n-i-j)*(r+i*g)*b-r*(t+(j-1)*b));
    应该改为max(f[i-1,j]+g*(j*b+t)*(n-i-j)-(r+(i-1)*g)*(b*j+t), f[i,j-1]+(r+i*g)*b*(n-i-j)-(r+i*g)*(b*(j-1)+t));
    减去的一个红塔的攻击,应该还要算上毒塔的加持。但这样的程序是无法通过数据的。您觉得对吗?

    Sunday, October 30, 2011 at 20:34 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*