状态压缩dp zoj3802

做这个题的时候看了看时间复杂度觉得应该是个贪心或者dp，然后贪心又很快被否定了，因为不具备贪心的一些特性，想了想觉得没什么思路。看了下网上的思路，真是让人拍案叫绝，算法的魅力就在于此啊。。

首先dp就意味着要寻找一些状态，我觉得500的状态太多了根本无从保存啊。网上的思路说难也不难，就是只保存下降的序列，因为能合并的只有下降的序列，上一个状态能够传递到下面的有不要当前，合并，当前值比递降序列最小的还小就归并，否则地将序列变成a[i];

我一下就明白了然后开始敲，TE！

各种优化

找能否合并由暴力找最小值变成j&(a[i]-1) TE

输入数所有除以2输出乘2这又减了一半时间复杂度还是TE

气的我肝都疼了看了看网上代码，用的滚动数组，哦。。。的确比我傻傻的用[500][8*500]少了250倍，改了改wa掉了我qu

于是我按照输入可能有一处理了一下ac！好开心~

代码如下

#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int maxa = ;

int dp[][*maxa];

int a[maxa];

int main(){

    int t;

    //freopen("in.cpp", "r", stdin);

    int n;

    scanf("%d", &t);

    while(t--){

        scanf("%d", &n);

        int sum = ;

        for(int i = ; i <= n ; i++){

            scanf("%d", &a[i]);

            a[i]/=;

            sum += a[i];

        }

        memset(dp, -, sizeof(dp));

        dp[][] = ;

        for(int g = ; g <= n; g++){

            int I = g%;

            int II = (g+)%;

            for(int j = ; j <= sum; j++){

                if(dp[II][j]!=-){

                    dp[I][j] =  max(dp[I][j],dp[II][j]);

                    if((a[g] -)&j){

                        dp[I][a[g]] = max(dp[I][a[g]], dp[II][j]+a[g]);

                    }else{

                        int mm = a[g];

                        int k = ;

                        int oo = a[g];

                        while(oo & j){

                            mm += oo*;

                            oo*=;

                        }//printf("%d %d\n", i, j, dp[i][]);

                        dp[I][j+a[g]] = max(dp[I][j+a[g]], dp[II][j] + mm);

                    }

                }

            }

        }

        int maxn = ;

        for(int i = ; i <= sum ;i++){

            maxn = max(maxn, dp[(n)%][i]);

        }

        printf("%d\n", *maxn);

    }

}

巴特西

状态压缩dp zoj3802

最新文章

热门文章