[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] 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

[ACM] POJ1011 POJ2362解题报告, 状态压缩

10年9月17号Update…
状态压缩BFS 40行水过.. 代码是POJ2362的, 一样的题.. 原来本文只有1011

#include <stdio.h>

bool dfs(int a[],int u,int n,int __s,int start)
{
    if (start==n)
        return true;
    for(int i=(1<<start);i<(1<<n);i+=(2<<start)) {
        if(i&u)
            continue;
        int count=0;
        for(int j=0;j<n;j++)
            count+=a[j]*((i>>j)&1);
        if(count!=__s)
            continue;

        int __u=u|i;
        int j;
        for(j=0;j<n && ((__u>>j)&1);j++);
        if(dfs(a,__u,n,__s,j)) {
            /* DEBUG
            for(int k=0;k<n;k++)
                if((i>>k)&1)
                    printf("%d ",a[k]);
            printf("\n");   */
            return true;
        }
    }
    return false;
}


int main()
{
    int N;
    scanf("%d",&N);
    while (N--)
    {
        int n,a[21],count=0;
        scanf("%d",&n);
        for (int i=0;i<n;i++)
        {
            scanf("%d",a+i);
            count+=a[i];
        }
        printf("%s\n",count%4?"no":(dfs(a,0,n,count/4,0)?"yes":"no"));
    }
    return 0;
}

Read More