`
xxx0624
  • 浏览: 28486 次
文章分类
社区版块
存档分类
最新评论

HDU2697+DP

 
阅读更多

Wa的版本。。。

/*
DP
dp[i][j]:前i个取某些个且cost不超过j得到的最大价值
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b)) 
const int maxn = 105;
const int maxm = 10005;
const int inf = 99999099;
const double pi=acos(-1.0);
const double eps = 1e-8;
struct Node{
    int len;
    bool Choosed;
    int maxVal;
}dp[ maxn ][ maxm ];
void init(){
    for( int i=0;i<maxn;i++ ){
        for( int j=0;j<maxm;j++ ){
            dp[i][j].maxVal = 0;
            dp[i][j].len = 0;
            dp[i][j].Choosed = false;
        }
    }
}
int cost[ maxn ];
int main(){
    int T;
    scanf("%d",&T);
    while( T-- ){
        int n,sum;
        scanf("%d%d",&n,&sum);
        //memset( dp,0,sizeof( dp ) );
        init();
        int SumCost = 0;
        int MinCost = inf;
        for( int i=0;i<n;i++ ){
            scanf("%d",&cost[i]);
            SumCost += cost[ i ];
            MinCost = min( MinCost,cost[i] );
        }
        if( MinCost>sum ) {
            printf("0\n");
            continue;
        }
        if( MinCost==sum ) {
            printf("1\n");
            continue;
        }
        if( sum>=SumCost ){
            printf("%d\n",n*n);
            continue;
        }
        
        int ans = 0;
        for( int i=0;i<n;i++ ){
            for( int j=cost[i];j<=sum;j++ ){
                dp[ i ][ j ].maxVal = 1;
                dp[ i ][ j ].len = 1;
                dp[ i ][ j ].Choosed = true;
                ans = 1;
            }
        }//init of dp
        
        for( int i=1;i<n;i++ ){
            for( int j=0;j<=sum;j++ ){
                if( dp[i-1][j].Choosed==false ){
                    if( j>=cost[i] ){
                        if( dp[i-1][j-cost[i]].maxVal+1>=dp[i-1][j].maxVal ){
                            dp[i][j].maxVal = dp[i-1][j-cost[i]].maxVal+1;
                            dp[i][j].len = 1;
                            dp[i][j].Choosed = true;
                        }
                        else {
                            if( dp[i-1][j].maxVal>dp[i][j].maxVal ){
                                dp[i][j].maxVal = dp[i-1][j].maxVal;
                                dp[i][j].len = 0;
                                dp[i][j].Choosed = false;
                            }
                        }
                    }
                    else {
                        if( dp[i-1][j].maxVal>dp[i][j].maxVal ){
                            dp[i][j].maxVal = dp[i-1][j].maxVal;
                            dp[i][j].len = 0;
                            dp[i][j].Choosed = false;
                        }
                    }
                }
                else{
                    if( j>=cost[i] ){
                        if( dp[i-1][j-cost[i]].maxVal-dp[i-1][j-cost[i]].len*dp[i-1][j-cost[i]].len+(dp[i-1][j-cost[i]].len+1)*(dp[i-1][j-cost[i]].len+1)>=dp[i-1][j].maxVal ){
                            dp[i][j].maxVal = dp[i-1][j-cost[i]].maxVal-dp[i-1][j-cost[i]].len*dp[i-1][j-cost[i]].len+(dp[i-1][j-cost[i]].len+1)*(dp[i-1][j-cost[i]].len+1);
                            dp[i][j].len = dp[i-1][j-cost[i]].len+1;
                            dp[i][j].Choosed = true;
                        }
                        else{
                            if( dp[i-1][j].maxVal>dp[i][j].maxVal ){
                                dp[i][j].maxVal = dp[i-1][j].maxVal;
                                dp[i][j].len = 0;
                                dp[i][j].Choosed = false;
                            }
                        }
                    }
                    else{
                        if( dp[i-1][j].maxVal>dp[i][j].maxVal ){
                            dp[i][j].maxVal = dp[i-1][j].maxVal;
                            dp[i][j].len = 0;
                            dp[i][j].Choosed = false;
                        }
                    }
                }
                ans = max(ans,dp[i][j].maxVal);
                //printf("dp[%d][%d].val = %d, len = %d, choose = %d \n",i,j,dp[i][j].maxVal,dp[i][j].len,dp[i][j].Choosed);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

Ac代码。。

dp[i][j]:前i个取某些个且cost不超过j得到的最大价值
dp[ i ][ j ] 通过 1 到 i-1 之间的dp[ k ][ ? ] ( 1<=k<i ) 来更新。

如果 dp[ i ][ j ]:取了第i个,则可能是被dp[ k ][ ? ]+ ??更新,反之则为dp[ i-1 ][ j ]

/*
DP
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b)) 
const int maxn = 105;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
int dp[ maxn ][ maxn ];
int a[ maxn ];
int main(){
	int T;
	scanf("%d",&T);
	while( T-- ){
		int n,sum;
		scanf("%d%d",&n,&sum);
		int MinCost = inf;
		for( int i=1;i<=n;i++ ){
			scanf("%d",&a[i]);
			if( a[i]<MinCost ) MinCost = a[i];
		}
		if( MinCost>sum ){
			printf("0\n");
			continue;
		}
		if( MinCost==sum ){
			puts("1");
			continue;
		}
		int ans = 0;
		memset( dp,0,sizeof( dp ) );
		for( int i=1;i<=n;i++ ){
			for( int j=0;j<=sum;j++ ){
				int cnt = 0;
				for( int k=1;k<=i;k++ ){
					cnt += a[ i+1-k ];
					if( cnt>j ) break;
					dp[i][j] = max( dp[i][j],dp[i-k][j-cnt]+k*k );
				}
				dp[i][j] = max( dp[i][j],dp[i-1][j] );
				ans = max( ans,dp[i][j] );
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}



分享到:
评论

相关推荐

    hdu 300+ AC 代码

    300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....

    HDU DP动态规划

    HDU的一题........HDU DP动态规

    HDU DP 题集

    动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...

    HDU DP题解

    HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高

    DP.rar_DP_hdu_动态规划_动态规划 C++

    动态规划DP题解 POJ HDU部分动态规划DP题解

    acmhdu1005

    hdu 1005.比较简单的一道题,有兴趣的可以看看。

    hdu 3341(ac自动机+状态压缩)

    hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...

    初探数位dp.pdf

    lazycal的集训队报告:初探数位DP 以HDU 2089,HDU 3652, URAL 1057等题目为例,介绍了数位DP的算法

    hdu 1176 免费馅饼

    dp的简单应用,状态转移方程dp[i][j] = max(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]) + p[i][j];注意开始点和终止点的判断

    OJ动态规划DP题目列表

    OJ动态规划DP题目列表 POJ SOJ HDU 动态规划题目

    HDU杭电ACM课件完整打包

    这是老师给我的哦,里面有完整版的HDU杭电ACM课件,还附有2000-2099的解题报告跟DP背包问题,如果你是acm的初学者,那么这是必须的,看了会有很大的帮助哦!

    动态规划DP结题报告

    动态规划DP题解 POJ HDU 动态规划解题报告

    JSU_动态规划_dp1

    最基础的DP题目解题报告,适合初学者!动态规划(DP1) http://acm.hdu.edu.cn/diy/contest_show.php?cid=20151 解题报告: 1001 计算直线的交点数 1002 FatMouse's Speed1003 Common Subsequence1004 Max Sum 1005 ...

    hdu4405_HDOJ_ACM_

    杭电oj4405,一道简单的概率dp题目

    acm课件动态规划题(杭电)(HDU)

    ACM培训好资料!能帮助你快速提高ACM AC题目的能力,值得一下

    wsgan001#algorithms-6#第09章_单调性优化1

    第09章 单调性优化9.1 斜率优化主要是针对线性模型,参考博客:HNOI2008 玩具装箱TOY 和【学习笔记】动态规划—斜率优化DP(超详细)+ HDU 3

    leetcode添加元素使和等于-programmer_practices:算法实践

    HDU-DP: jzOffer: 2018_xz LeetCode 2019/5/7: 18. 4Sum 19. Remove Nth Node From End of List 20. Valid Parentheses 21. Merge Two Sorted Lists 22. Generate Parentheses 18 3 sum 扩展版, 外层多套一个循环...

    acm部分模板

    图论 dp 部分模板 内涵几道poj以及hdu上的例题..............................................................

    leetcode下载-campus_recruitmen_questions:2021年最新整理,5000道秋招/提前批/春招/常用面试题,包

    3.DP+四边形不等式优化(hdu 3506 Monkey Party) 4.快餐(hoj 1005 fast food) 5.hoj 1031完全背包Piggy-Bank 6.数字金字塔(hoj 1058Number Triangles) 7.肥猫的表亲(hoj 1061Fat Cat's cousin II) 8.加建楼梯...

    kuangbin acm模板超级好用

    2.18.1 HDU4656 卷积取模 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.19 其它公式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.19.1 Polya . . . ....

Global site tag (gtag.js) - Google Analytics