[ACM] POJ 2133 Cow Imposters, easy DP + BFS

简单DP + BFS
牌子之间两两组合出新牌子, 新产生的牌子只需与原始的号码两两组合即可,即,不用考虑两个新牌子组合的情况,因为两个新牌子组合的结果必然等价与一个新牌子和原始牌子组合的结果, 否则会超时。

很自然的就可以用类似BFS里的队列来做, 我由此引发的思考是, 这种新牌子和原始牌子组合到达新point, 和BFS的思想是十分一致的, 我可以把每一个原始牌子看作一个方向, 牌子号码的每一位是一维空间。 比如 01001 这个原始牌子, 对应了一个五维空间, 这个原始牌子的方向就是 ( 0, 1, 0, 0, 1 ) 。 题目就能抽象为, 给出一个B维的空间和可以走的E个方向, 问你能到达离某个点最近的维度
Read More

[ACM] POJ 1205, 简单DP

DP就是每次在原序列右边加一个city的时候 (此时n个city) 只要看前一个状态 (n-1个city) 最右边的city的情况
也就是记录n个city时的三个状态 xxxV xxx> xxx<
xxxV 和 xxx< 的数量和就是要求的结果, xxx>是记录一下如果允许向右流水那么方案的数量
状态转移即为右图
然后dp[100]结果超过long long, 于是用BigInteger, 写这个报告的原因也是第一次用Java交OJ..

代码:


import java.math.*;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		BigInteger dp[][]=new BigInteger[101][2];
		dp[1][0]=BigInteger.ONE;
		dp[1][1]=BigInteger.ZERO;
		for(int i=2;i<=100;i++) {
			dp[i][0]=dp[i-1][0].add(dp[i-1][0]).add(dp[i-1][1]);
			dp[i][1]=dp[i-1][0].add(dp[i-1][1]);
		}
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()) {
			int a=sc.nextInt();
			System.out.println(dp[a][0].add(dp[a][1]));
		}
	}
}

[ACM] POJ 1173 解题报告, DP, 逐位确定

我表示是跟着黄伟牛混的.. 他写的报告难以称作报告.. 题目一抄写两句话代码一贴万事, 自己琢磨了好久, 记录一下, 我记性不好喜欢写的详细一点以后自己可以查.. (拓展阅读: 刘未鹏牛的<为什么你应该(从现在开始就)写博客> )

快放假了, ACM + GRE 加油, 不拼命的下场只有一个, 平庸.. 哞

第一问 total number of symbols in BC(n,k,m) 比较容易, 简单DP

dp[n][k][m]=∑dp[n-i][k-1][m]     , i∈[1,m]

第二问 yzhw口口声声“经典的逐位确定方法”..

也就是说, 我们来看 “1111010”(从0位到6位), 简单的讲从高位(0)到低位(6)每一位如果有1, 那么就看, 如果这一位是0, (继承前面的高位后) 低位能形成多少种组合, 把这个组合数加到rank中.
流程是 1[0xxxxx]能有多少组合 即求0xxxxx符合k-1和m的组合(直接用前面求出的dp数组即可, 虽然前面求的是1xxxxx, 但是和0xxxxx数量是一样的), 然后11[0xxxx]能有多少种, 遇到0跳过, 最后看11110[0x]

但是这样并不完全缜密, 我们考虑”10011000″的情况, 按上面的算法进行到第3位的时候, 100[0xxxx], 这个0xxxx是可能产生00011这种组合的, 而放入原文就变成了10000011, 0的长度就超过了. 所以我们想出来的办法是把 0-1 (不包括1到0) 交界处的那个1单独考虑, 看前面有多少位0然后详细说明. 比如100[0xxxx], xxxx只能是以1开头的, 10[0xxx], xxx只能是1xx或者01x, (11x到哪去了? 11x不是在这里的 [特殊情况] 内考虑的, 好好想一下.. 没法讲的太清楚)

代码如下, 写的时候很有自己的想法, 多推敲推敲最后的产品和yzhw的也八九不离十了.. 这个代码还是很精简很漂亮的


#include <stdio.h>
#include <string.h>
#include <algorithm>

int main() {
	int dp[34][34][34];
	memset(dp,0,sizeof(dp));
	//DP
	for(int m=1;m<=33;m++) {
		for(int i=1;i<=m;i++)
			dp[i][1][m]=1;
		for(int k=1;k<33;k++)
			for(int n=k;n<33;n++) {
				if(!dp[n][k][m])
					break;
				for(int i=1;i<=m;i++) {
					if(n+i>33)
						break;
					dp[n+i][k+1][m]+=dp[n][k][m];
				}
			}
	}

	int n,k,m;
	scanf("%d%d%d",&n,&k,&m);
	printf("%d\n",dp[n][k][m]);

	int N;
	scanf("%d",&N);
	while(N--) {
		char a[34];
		scanf("%s",a);
		char color='1';
		int rank=0;
		int kRemain=k;
		int head=0;
		for(int p=0;a[p]!='\0';p++) {
			if(color==a[p])
				continue;
			if(color=='1') {
				color='0';
				kRemain--;
				for(int i=head+1;i<p;i++)
					rank+=dp[n-i][kRemain][m];
			}
			else {
				color='1';
				kRemain--;
				for(int i=std::min(n-1,head+m);i>p;i--)
					rank+=dp[n-i][kRemain][m];
			}
			head=p;
		}
		printf("%d\n",rank);
	}

	return 0;
}

[ACM] POJ 1887 2533 解题报告, LIS的nlogn算法..

记录到当前位置combo数为k的尾巴的最小值, 比如 1 3 2 6, 则 dp[combo]=tail 罗列为 dp[1]=1, dp[2]=2 (1,2的尾巴比1,3等小), dp[3]=6, combo最大为6. 然后再多加一位就看能不能更新前面combo数对应的tail, 让tail更小; 当然还看combo数能不能+1. 比如1 3 2 6再加个5, dp[3]就=5 (1,2,5的tail比1,2,6的tail小), 不加5加7就多一个dp[4]=7. 因为dp[combo]值相对于combo数是递增的, 所以可以二分查找实现nlogn.

这两个是买一送一的题目.. 1887的二分写的有点蛋疼.. 2533要求不能相等, 就加了个标记每次对二分的两个指针p0,p1, 和中点(p0+p1)/2看一下, 重复就continue, 不重复一样做, 省得麻烦.. 想了一下还可以前面严格<, 后面可以>=, 这样更新tail的时候就不会重复产生影响.

代码点下面:
Read More

[ACM] POJ 2430 解题报告, 状态压缩DP, 奶牛你太懒了..

从左到右DP, 存储哪里有奶牛以后排序, 同一个x坐标的上下奶牛合并.. 0没有 1上 2下 3都有
随着奶牛的位置x从左到右DP, 需要记录的状态是dp[i][p][k], p是在x处的奶牛圈起来的方式, 我记的是 0没圈(这就初始状态可能) 1圈上 2圈下 3两个一起圈 4两个分开圈, 记录每个可能的k和对应的面积最小值
状态转移比较麻烦.. 我是又分两个状态之间的圈圈怎样互相结合来枚举,  0不结合 1上边延伸出去 2下边 3两边一起延伸 4两边分开延伸. 应该还有更巧妙的方法.. 不想再碰这题了
172ms 直接大数组20M内存..代码点下面
Read More

[ACM] POJ2353 POJ3612解题报告

POJ2353
穷逼DP时间复杂度O(n*m*m), 我想的就是这个..
牛逼DP时间复杂度O(n*m), 每一个room的状态都只能由左下右三个room决定, 从底向上双向递归..

POJ3612
把dp[i][h]分成两部分求解, 两部分可以分别以O(100)预处理, 求dp[i][h]是O(1), 所以整个复杂度只有O(n*100), 很棒
引用牛kevin0602的讲解(他的博客已经进不去了.. 不知为何)

先分h’大于h和小于h两种情况,这方程可写为f(n, h) = (H[i]-h)^2 + min { -C*h + min { f(n-1, h’)+C*h’ } (for h’ >= h),C*h + min { f(n-1, h’)-C*h’ } (for h’ < h) },这样就把h’放在一起了,现在定义low(n, h) := min over h' >= h { f(n, h’)+C*h’ },high(n, h) := min over h’ < h { f(n, h')-C*h' },则可方程进一步写为f(n, h) = (H[i]-h)^2 + min { -C*h+low(n-1, h), C*h+high(n-1, h) }。在计算第n个电线杆的时候,low(n-1, h)和 high(n-1, h)用双重DP的方法可以在O(100)*3的时间内算出,则总时间复杂度为O(N*100)。

双向DP有点类似双向BFS, 两次BFS后可以O(1)求通过某点的入口-出口路径, 这两个题每一个状态都是可以表示成从两个状态比较来. 以后遇到类似的题目要警觉一下.. 或许还有三向之类的衍生..

代码:
Read More

[ACM] POJ1067解题报告, Beatty贝蒂数列

无意看到的题目.. 因为是中文的就猫了一眼, 觉得挺水就做做, 结果一做就是一下午.. NOI还有点名堂

开始觉得就是博弈+简单DP, 右图每一个格子 (a, b) , 玩家一次取石子以后能变成的状态是 (a-i, b) , (a, b-i) , 或者 (a-i, b-i) , 只要路线上存在lose, 赋值为win, 否则赋值lose. 整个表格是对称的. 自底向上DP就可以解决.

然后看了discuss, 存在O(1) 的算法..

Beatty sequence Wiki 讲解 , 看一下就了了..

The positive irrational number r\, generates the Beatty sequence

\mathcal{B}_r = \lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor,... = ( \lfloor nr \rfloor)_{n\geq 1}

If r > 1 \,, then s = r/(r-1)\, is also a positive irrational number. They naturally satisfy

\frac1r + \frac1s = 1 \,

and the sequences

\mathcal{B}_r = ( \lfloor nr \rfloor)_{n\geq 1} and
\mathcal{B}_s = ( \lfloor ns \rfloor)_{n\geq 1}

form a pair of complementary Beatty sequences.

For r = the golden mean, we have s = r + 1. In this case, the sequence ( \lfloor nr \rfloor), known as the lower Wythoff sequence, is

  • 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, … (sequence A000201 in OEIS).

and the complementary sequence ( \lfloor ns \rfloor), the upper Wythoff sequence, is

  • 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, … (sequence A001950 in OEIS).

上下两个数列整好组成 lose 状态的坐标 (1,2) (3,5) (4,7) … 至于为什么等我有空会思考update一下 =D 好神奇阿

其中r是黄金分割律, 即 (1+sqrt(5))/2

则如果m在第一个数列里,则

m=[nr]=nr-x
m/r=n-x/r

其中x属于[0,1) , 先求出n再判断m/r是否在等式右边的区间里即可. 再返回n判断输入的b是否在二队列中相应的位置

Code:

#include <stdio.h>
#include <math.h>
#include <algorithm>

//return num in Beatty sequence(r=golden mean), -1 if not belong to
int Br(int m) {
    static const double P=(1+sqrt(5.0))/2;
    double foo=m/P;
    int n=(int)foo;
    if(foo-n>0.999999)
        n++;
    n++;
    if(foo>(n-1/P))
        return n;
    else
        return -1;
}

int main() {
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF) {
        if(a>b)
            std::swap(a,b);
        int foo=Br(a);
        bool win=true;
        if(foo!=-1)
            if(a+foo==b)
                win=false;
        if(win)
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}

[ACM] POJ1159解题报告, LCS

引用大牛lnmm的思路

设ch[1]..ch[n]表示字符串1至n位,i为左游标,j为右游标 ,则i从n递减,j从i开始递增。
min[i][j]表示i和j之间至少需要插入多少个字符才能对称,初始置全0 ,我们最终需要得到的值是min[1][n]. 则
if(ch[i]==ch[j])                                    //如果两个游标所指字符相同,向中间缩小范围
min[i][j]=min[i+1][j-1];
else
min[i][j] = 1 +  (min[i+1][j]和min[i][j-1]中的较小值);     //如果不同,典型的状态转换方程

画个图

i\j  1    2    3    4    5
1    0    *    *    *    *
2    0    0    *    *    *
3         0    0    *    *
4              0    0    *
5                   0    0

求右上的三角形即可, 三个方向, 左, 下, 左下, 和算法导论里353页的图思路差不多, 意思不一样而已.
一个自以为比较有意思的空间优化是, 把头顺时针转45度看那个三角形.. 不讲了麻烦, 上代码..

404K 344MS G++

#include <stdio.h>

int main()
{
    int n;
    char a[5010];
    scanf("%d",&n);
    while(getchar()!='\n');
    scanf("%s",a);

    int c[10010];
    for(int i=2;i<=2*n;i++) {
        c[i]=0;
    }

    for(int x=1;x<=n-1;x++)
        for(int i=1;i<=n-x;i++) {
            int j=i+x;
            char ai=a[i-1],aj=a[j-1];
            if(ai==aj)
                continue;
            c[i+j]=c[i+j-1]<c[i+j+1]?c[i+j-1]:c[i+j+1];
            c[i+j]++;
        }
    printf("%d\n",c[1+n]);

    return 0;
}

[ACM] POJ1185解题报告 状态压缩DP

思路和网上的都差不多, 我另外开了程序算出每一行可能的情况直接copy进 stack[] 中..耍流氓.. 看起来直观点
引用一下大牛BYVoid的思路, 不自己写了

较难看出的动态规划问题。注意到数据范围N≤100;M≤10,发现每行的宽度都不大,所以可以考虑把一行看成一个状态,表示该行的布置方案。每行的布置方案可以预先处理出,由数学知识可以算出,每行最多的布置方案数也不过60个而已。

状态设定

F[i,a,b]为前i行,第i行的方案为A[a],第i-1行的方案为A[b]的最大炮兵数。

状态转移方程

  • F[i,a,b]=Max{ F[i-1,b,c] + P[a] }

其中c为i-2行的布置方案,a,b,c应保证互不冲突,即放置方案中炮兵都在平地上,且不会互相攻击到。

目标结果

  • Ans=Max{F[N,a,b]}

中间进行过一次错误的优化, 认为如果, 比如
画个图..

    HHPH
    PPPP
    PPPP
    HHPH  (红色代表有炮)

1001比1101少了一个1, 那么1101得出的结果至少不会比1001差, 可以剪掉1001. 比如上图的第三行, 没有炮的情况就可以省去,.我当时的想法是如果省掉第三行的炮, 放在第四行唯一的P上(其他情况也是相似),  第四行以下面临的情况就会比之前更加严峻, 从而不会得出更好的结果, 顶多一样.

但是我并没有考虑第三行能对第一行也产生影响 (造成这个错误的原因是状态压缩DP只记录近两行. 虽然没有明面上写, 但是情况已经记录在得分中了). 第三行的P不放炮, 则第一行和第四行都能放, 结果就更好了.

遗留问题, 如何才能在类的定义中实现二维数组的动态分配?

我写成这样

public:
    int *(a[60]);
    State (int m=0) {
        M=m;
        for(int i=0;i<stackN;i++) {
            a[i]=new int[stackN];
            memset(a[i],0xff,sizeof(int)*stackN);
        }
    }

能够compile, 在另开的程序里也没有问题, 但是在题目中答案就不一样, 我跟踪了, 在 s[i].dp(s[i-1]) 的过程中 s[i-1].a[][] 会莫名发生改变, 实际上又没有对它进行任何操作. 值得一提的是release和debug得出的答案不一样, 根据经验应该是内存的什么问题.. 也有可能是类里动态分配内存就不对头, 因为在类中定义变量不能用new..  开学去问问看

Code: (其实是我第一次用类.. 这个问题有点绕, 于是尝试封装=D )

Read More