hdu5693D++游戏区间DP-暴力递归

主要的收获是。。如何优化你递推式里面不必要的决策

之前的代码

这个代码在HDU超时了，这就对了。。这个复杂度爆炸。。

但是这个思路非常地耿直。。那就是只需要暴力枚举删两个和删三个的情况，于是就非常耿直的枚举是哪两个n^2,是哪三个n^3

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int T,n,m;

int a[305],d[305];

bool f[305][305];

//定向从左往右删除

int dp[305][305];

int  dfs(int l,int r){

    // printf("l%d r%d\n",l,r);

    if(dp[l][r]!=-1) return dp[l][r];

    if(l>=r) return dp[l][r]=0;

    int i,j,k,p=0;

    //枚举删两个

    for(i=l;i<r;++i)

        for(j=i+1;j<=r;++j)

        {

            //删i,j

            //如果dfs(x,y)==y-x+1,则说明[x,y]能被完全删除

            // printf("part:: i%d j%d\n",i,j);

            if(f[i][j]&&(dfs(i+1,j-1)==j-i-1)){

                // printf("Tpart:: i%d j%d\n",i,j);

                p=max(p,(j-i+1)+dfs(l,i-1)+dfs(j+1,r));

                // printf("VAL:: %d\n",p);

            }

        }

    //枚举删三个

    for(i=l;i<r;++i)

        for(j=i+1;j<r;++j)

            for(k=j+1;k<=r;++k)

            {

                // printf("part:: i%d j%d k%d\n",i,j,k);

                if(f[i][j]&&f[j][k]&&(a[j]-a[i]==a[k]-a[j])&&(dfs(i+1,j-1)==j-i-1)&&(dfs(j+1,k-1)==k-j-1)){

                    // printf("Tpart:: i%d j%d k%d\n",i,j,k);

                    p=max(p,(k-i+1)+dfs(l,i-1)+dfs(k+1,r));

                    // printf("VAL:: %d\n",p);

                }

            }

    return dp[l][r]=p;

}

void solve(){

    memset(dp,0,sizeof(dp));

    int l,r,i,j,k,len;

    for(len=2;len<=n;++len){

        for(l=1;l<n;++l){

            r=l+len-1;

            printf("DP l%d r%d\n",l,r);

            if(l>=r) continue;

            for(i=l;i<r;++i){

                for(j=i+1;j<=r;++j){

                    printf("part2 ASK (%d,%d) (%d,%d)\n",l,i-1,j+1,r);

                    if(f[i][j]&&dp[i+1][j-1]==j-i-1) {

                        // printf("part2 ask (%d,%d) (%d,%d)\n",l,i-1,j+1,r);

                        dp[l][r]=max(dp[l][r],(j-i+1)+dp[l][i-1]+dp[j+1][r]);

                    }

                }

            }

            for(i=l;i<r;++i){

                for(j=i+1;j<r;++j){

                    for(k=j+1;k<=r;++k){

                        printf("part3 ASK (%d,%d) (%d,%d)\n",l,i-1,k+1,r);

                        if(f[i][j]&&f[j][k]&&(a[j]-a[i]==a[k]-a[j])&&dp[i+1][j-1]==j-i-1&&dp[j+1][k-1]==k-j-1){

                            // printf("part3 ask (%d,%d) (%d,%d)\n",l,i-1,k+1,r);

                            dp[l][r]=max(dp[l][r],(k-i+1)+dp[l][i-1]+dp[k+1][r]);

                        }

                    }

                }

            }

        }

    }

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        int i,j,k;

        for(i=1;i<=n;++i) scanf("%d",a+i);

        for(i=1;i<=m;++i) scanf("%d",d+i);

        memset(f,0,sizeof(f));

        for(i=1;i<n;++i)

            for(j=i+1;j<=n;++j)

                for(k=1;k<=m;++k) f[i][j]|=(a[j]-a[i]==d[k]);

        solve();

        printf("%d\n",dp[1][n]);

    }

    return 0;

}

我们发现了一个枚举的方法是

在区间[l,r],要么我们只取l,r这两个数删掉

要么枚举在区间[l,r]内的分割点k,于是我们只需要考虑l,k,r这三个数能不能删掉

注意到我们l,r是必选的。。这样就不能形成最后一次删掉的数字在中间

于是我们枚举l,r不是必选的情况，递归分成两个子区间，将这个不选的决策交给子区间，这样我们就发现有了这个分解的步骤

即使采用了上述前两个策略。。凭借只用短长度区间l,r全选和,l,k,r全选就能形成所有的决策，我认为这个想法是非常巧妙的

虽然大佬们认为可能这很显然Orz，但是不得不说这种递归策略非常巧妙。。可能是我还没掌握精髓吧。。

放上1499ms/3000ms的代码

细节：小心r越界，因为我的len一直枚举到n,

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int T,n,m;

int a[305],d[305];

bool f[305][305];

//定向从左往右删除

int dp[305][305];

void solve(){

    memset(dp,0,sizeof(dp));

    int l,r,i,j,k,len;

    for(len=2;len<=n;++len){

        for(l=1;l<n;++l){

            r=l+len-1;

            // printf("DP (%d,%d)\n",l,r);

            if(r>n) continue;

            if(l>=r) continue;

            // printf("ASK (%d,%d) \n",l+1,r-1);

            if(f[l][r]&&dp[l+1][r-1]==r-l-1)

            dp[l][r]=max(dp[l][r],2+dp[l+1][r-1]);

            for(i=l;i<r;++i) {

                // printf("ASK (%d,%d) (%d,%d)\n",l,i,i+1,r);

                dp[l][r]=max(dp[l][r],dp[l][i]+dp[i+1][r]);//当前区间保留头尾的情况

                                                            //这一句是我所需要的精华。。

            }

            for(k=l;k<=r;++k){

                // printf("ASK (%d,%d) (%d,%d)\n",l+1,k-1,k+1,r-1);

                if(f[l][k]&&f[k][r]&&(a[k]-a[l]==a[r]-a[k])&&dp[l+1][k-1]==k-l-1&&dp[k+1][r-1]==r-k-1){

                    dp[l][r]=max(dp[l][r],r-l+1);

                }

            }

        }

    }

}

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        int i,j,k;

        for(i=1;i<=n;++i) scanf("%d",a+i);

        for(i=1;i<=m;++i) scanf("%d",d+i);

        memset(f,0,sizeof(f));

        for(i=1;i<n;++i)

            for(j=i+1;j<=n;++j)

                for(k=1;k<=m;++k) f[i][j]|=(a[j]-a[i]==d[k]);

        solve();

        printf("%d\n",dp[1][n]);

    }

    return 0;

}

巴特西

hdu5693D++游戏区间DP-暴力递归

最新文章

热门文章

巴特西

hdu5693D++游戏 区间DP-暴力递归

最新文章

热门文章

hdu5693D++游戏区间DP-暴力递归