| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1209 人关注过本帖
标题:求AC代码及详细解释(也就是推导思路)
只看楼主 加入收藏
heartnheart
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:335
专家分:1096
注 册:2009-7-10
结帖率:100%
收藏
已结贴  问题点数:100 回复次数:13 
求AC代码及详细解释(也就是推导思路)
Wujitu的RP守恒
时间限制:1500 ms  |  内存限制:8192 KB
描述
话说天下的RP是守恒的,你的RP高了,我的RP可能就低了,你今天RP高了,明天RP可能就低了。我们的RP总是在高高低低中不断变化。有些事情做了是可以涨RP的,有的事情做了是要降RP的。
Wujitu在发现了这个道理后,决定在期末考试前多多积累人品。他发现,他做的每件事情对RP有如下影响:
(1) 他做了的第一件事情是涨RP的
(2) 如果他做的上一件事情是涨RP的,那么他做的下一件事情是降RP的
(3) 如果他做的上一件事情是降RP的,那么他做的下一件事情是涨RP的
Wujitu现在积攒的人品是0。涨RP记为RP值增加,降RP记为RP值减少。
Wujitu在期末考试前有N件事情可以做,每件事情都有自己的RP系数。对于这些事情,Wujitu只可以有两种选择:做,不做。事情的先后顺序是一定的,也就是说Wujitu只可以按照给定好的顺序选择做不做该事情。
现在请你帮助Wujitu在期末考试之前,积攒到最多的RP。


输入
每组数据包括两行,第一行有一个整数N(N<=1000000),代表有N件事情;第二行有N个正整数,代表每件事情的RP值Ri[正数]
Ri<=1000000

输出
输出结果仅包含一个整数,即Wujitu在期末前能积攒的最大RP值

样例输入
1
1
4
1 3 1 2
样例输出
1
4

希望能给出AC代码以及详细解释,这道DP题好像有后效应,不知道怎么做,望大牛赐教

在下面提交,谢谢!
http://www.
搜索更多相关主题的帖子: 解释 代码 推导 思路 
2010-07-26 22:31
heartnheart
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:335
专家分:1096
注 册:2009-7-10
收藏
得分:0 
自己顶一个~
2010-07-27 09:37
heartnheart
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
帖 子:335
专家分:1096
注 册:2009-7-10
收藏
得分:0 
顶起!
2010-07-27 19:08
kahuna
Rank: 1
等 级:新手上路
帖 子:24
专家分:5
注 册:2007-10-30
收藏
得分:0 
排序?
2010-07-27 20:55
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
过了一天还没人回这个问题吗?
在下算法白痴,就不趟这混水了,帮忙顶顶吧~~
2010-07-27 22:15
Justfeeling
Rank: 2
等 级:论坛游民
帖 子:26
专家分:47
注 册:2010-2-15
收藏
得分:0 
菜鸟飘过~~顶一个
2010-07-27 22:21
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
收藏
得分:0 
不知道格式,根本无法验证啊。。。。。。连写个A+B的都提示
编译错误信息:
collect2: ld returned 1 exit status

2010-07-28 11:06
pangding
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:北京
等 级:贵宾
威 望:94
帖 子:6784
专家分:16751
注 册:2008-12-20
收藏
得分:0 
7 楼的代码贴出来看一眼。
2010-07-28 12:02
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
收藏
得分:0 
程序代码:
#include <stdio.h>
int main()
{
    int n,rp[1000000],count;
    int i,j;
    long maxRp;
    while(scanf("%d",&n) != EOF)
    {
        maxRp=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&rp[i]);
        }
        for(i=0;i<n;i++)
        {
            long temp =0;
            for(j=i,count=0;j<n;j++,count++)
            {               
                if(count%2==0)
                {
                    temp+=rp[j];
                    if(maxRp<temp)
                        maxRp=temp;
                }
                else
                {
                    temp-=rp[j];
                    if(temp<0)
                        break;
                }
            }
        }
        printf("%ld\n",maxRp);
    }   
}


这是我的代码,但是我验证不了啊,不知道格式是怎样的
2010-07-28 12:50
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
收藏
得分:0 
题意理解错了,我再看看
2010-07-28 12:53
快速回复:求AC代码及详细解释(也就是推导思路)
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.040486 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved