首页 > ACM题库 > HDU-杭电 > HDU 1574 RP问题-动态规划-[解题报告] C++
2013
12-12

HDU 1574 RP问题-动态规划-[解题报告] C++

RP问题

问题描述 :

在人类社会中,任何个体都具有人品,人品有各种不同的形式,可以从一种形式转换为另一种形式,从一个个体传递给另一个个体,在转换和传递的过程中,人品不会消失,也不被能创造,这就是,人品守恒定律!
人品守恒定律更形象的描述,当发生一件好事,你从中获利,必定消耗一定量RP;当发生一件不幸的事,你在其中有所损失,必定积攒一定量RP。
假设在一个时间段内在你身上可能会发生N个事件,每个事件都对应一个RP变化值a、RP门槛值b和获益值c。当RP变化值a为正,获益值c必定为负,只有你当前的RP值小于等于RP门槛值b的时候,此事件才有可能发生,当此事件发生时,你的RP值将增加|a|,获益值将减少|c|。反之,当RP变化值a为负,获益值c必定为正,只有你当前的RP值大于等于RP门槛值b的时候,此事件才有可能发生,当此事件发生时,你的RP值将减少|a|,获益值将增加|c|。
一个事件在满足上述RP条件的前提下,未必会发生。假设在这段时间之前你所具有的RP值和获益值都为0,那么过了这段时间后,你可能达到的最大获益值是多少?
注意:一个人的所具有的RP值可能为负。

输入:

输入数据的第一行为一个正整数T,表示有T组测试数据。每组测试数据的第一行为一个正整数N (0 < N <= 1000),表示这个时间段在你身上可能发生N个事件。接下来N行,每行有三个整数a, b, c (0 <= |a| <= 10, 0 <= |b| <= 10000, 0 <= |c| <= 10000)。这N个事件是按照输入先后顺序先后发生的。也就是说不可能先发生第i行的事件,然后再发生i � j行的事件。

输出:

对应每一组输入,在独立一行中输出一个正整数,表示最大可能获益值。

样例输入:

3
1
-1 0 1
2
10 200 -1
-5 8 3
3
-5 0 4
10 -5 -5
-5 5 10

样例输出:

1
2
9

 这个,RP在竞赛中的重要性就不需要多说了~ 这是一道典型的动态规划,dp[NN],用来表示 RP为 NN 时 最大收益率

因为可能为负值,故采取加一个权值使其为正数。 注意下初始化问题,然后还有 a 的正负关系的状态转移方程虽然一样,但是,循环方式不同,一个从小到大,一个从大到小,为什么需要这样, 不解释,嘿嘿!

状态转移方程:dp[i+a]  = max(dp[i]+c,dp[i+a]);

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define INF 99999999
#define NN 20010
int RP[NN];
int l,r,max, rp;
int main()
{
	int T,n,a,b,c,i,x;
	scanf("%d",&T);
	while(T--){
	
		scanf("%d",&n);	
		for(i=0;i<NN;i++)RP[i] = -INF;
		l=r= 10000;
		max = 0;
		RP[l]=0;
		while(n--){
			scanf("%d%d%d",&a,&b,&c);
			b +=10000;
			if(a < 0){
				for(i=b;i<=r;i++)
					if(RP[i] != -INF){
						x = RP[i] +c;
						//if(RP[i+a] == -INF)RP[i+a] = 0;
						if(RP[i+a] < x)
							RP[i+a] = x;
					}
				l +=a;
			}
			else if (a>0){
				for(i=b;i>=l;i--){
					if(RP[i] !=-INF){
						x = RP[i] +c;
						//if(RP[i+a] == -INF)RP[i+a] = 0;
						if(RP[i+a] < x)
							RP[i+a] = x;
					}
				}
				r +=a;
			}
		}
		for(i=l;i<=r;i++)
			if(RP[i] > max &&RP[i] != -INF)max = RP[i];
		printf("%d\n",max);
	
	}
	return 0;
}

解题报告转自:http://blog.csdn.net/surfacedust/article/details/6643308


  1. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  4. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  5. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  6. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?