首页 > 代码库 > hdu 1003 Max Sum 最大字段和 dp
hdu 1003 Max Sum 最大字段和 dp
今天看了一上午dp。看不太懂啊。dp确实不简单。今天開始学习dp,搜了杭电的dp46道,慢慢来吧。白书上的写的
又不太具体,先写几道题目再说。
。。
题目连接: id=516&page=1">点击打开链接
思路:就是当当前的和是小于0的时候就又一次计数。大于或者等于0的时候都相加。。。
id=516&page=1">代码:
/* Name: Copyright: Author: Date: 08/08/15 08:41 Description: */ #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<vector> #include<set> #include<string> #include<algorithm> using namespace std; int a[100005]; int main() { int T,i,n; cin >> T; int cnt = 0; while(T--) { cnt++; cin >> n; for(i=1; i<=n; i++) cin >> a[i]; int start = 1,end = 1,sta = 1; int b=0, sum = -0x7fffffff; for(i=1; i<=n; i++) { if(b >= 0) b += a[i]; else { b = a[i]; start = i; } if(b > sum) { sta = start; end = i; sum = b; } } printf("Case %d:\n",cnt); cout << sum << " " << sta << " " << end << endl; if(T) cout << endl; } return 0; }
hdu 1003 Max Sum 最大字段和 dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。