• P1651 塔


    -----------------

    链接:Miku

    -----------------

    这是一道dp题,我么很容易发现这点。

    数据范围很大,如果直接用两个塔的高度当状态,很危险,我们就必须要考虑一下优化了。

    两个塔的高度其实是没有没要的,我们追求的是差值,那么,比如6 8 和7 9,很明显,无论我们怎么放,第二个就是第一个加1,无论如何。

    那么我们没必要存第一个状态的,很显然,第二个更优

    ---------------------------

    我们定义方程 dp[i][j],其中i是第几个积木,j是两个塔的高度差值,它的值是最矮的塔的高度,很明显,对于每一个积木,我们有四种可能

    放在最高的,不放,放在最低的,并且放完了仍然低于高塔或者高于高塔。

    答案是dp[n][0]

    ---------------------------

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int dp[60][501000];
    int n;
    int a[60];    
    int sum;
    int main(){
        memset(dp,-0x7f7f,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        dp[0][0]=0;
        for(int i=1;i<=n;++i){
            for(int j=sum;j>=0;--j){
                dp[i][j]=max(max(dp[i-1][j],dp[i-1][j+a[i]]+a[i]),dp[i-1][abs(j-a[i])]+max(0,a[i]-j));
            }
        }
        if(dp[n][0]!=0)
        cout<<dp[n][0];
        else{
        cout<<-1;
        }
        return 0;
    }
    Ac

    ---------------

  • 相关阅读:
    [转]进程的用户栈和内核栈
    什么是URL,URL格式
    设计灵感
    Spring源码学习相关记录
    HTML图片标签路径解析
    一次Spring Bean初始化顺序问题排查记录
    是要面向对象,还是简单粗暴?
    2018/07/26学习节点记录
    数据结构-堆 Java实现
    2018 ICPC 徐州邀请赛 总结
  • 原文地址:https://www.cnblogs.com/For-Miku/p/12217500.html
一二三 - 开发者的网上家园