hdu 1003 Max Sum 단순 동적 계획

1366 단어
간단한 동적 기획이지만 ac율이 4분의 1보다 낮고 상태 이동 방정식:
dp[i]=max(dp[i-1]+a[i],a[i])
참고 사항:
케이스 사이에 공백이 있어요.
입력한 최소 음수는 -1000입니다.
여러 조의 답안이 첫 번째 뜻을 찾아내면 처음부터 편리하게 첫 번째 가장 큰 것을 얻고 이불을 출력한 다음break;
/*************************************************************************
	> File Name: hdu1231.cpp
	> Author: yang
	> Mail:[email protected] 
	> Created Time: 2014 08 24      20:01:52
 ************************************************************************/

#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
#define N 100005
int main(){
	int n;
	int a[N],dp[N],start[N],t,p=1;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		int flag=0,cou=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			dp[i]=0;
		}
		int x=1;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++){
			if(dp[i-1]+a[i]>=a[i])
				dp[i]=dp[i-1]+a[i];
			else{
				x=i;
				dp[i]=a[i];
			}
			start[i]=x;
		}
		cou=-1002;
		printf("Case %d:
",p++); for(int i=1;i<=n;i++) if(dp[i]>cou) cou=dp[i]; for(int i=1;i<=n;i++){ if(cou==dp[i]){ cout<<dp[i]<<" "<<start[i]<<" "<<i<<endl; break; } } if(t!=0) cout<<endl; } }

좋은 웹페이지 즐겨찾기