HDU(1003)动态规划

这道题虽然有很多种解法，但我一直尝试着用动态规划解，刚入门，用起来很不顺手，其中出现了很多错误，很多的意想不到，希望通过这道题，对动态规划能够更进一步的了解。

这道题是典型的也是动态规划中最简单的一道题，求最大子串和的问题。

第一步：分解出子问题。

本题的子问题是：dp[i] 代表前i个数中最大子串的和 ；

第二步：通过递归或递推求出子问题的最优解。

本题中的状态转移方程为：if ( dp[i-1] < 0 ) dp[i] = a[i]  ;

else  dp[i] = dp[i-1] + a[i] ;

#include<iostream>
#include<stdio.h>
using namespace std ;



int main()	{
	int n ;
	cin >> n ;
	int t = 1 ;
	while(n--)	{
		int a[110000] , dp[110000] ;
		int m ;
		cin >> m ;
		for(int i =  0 ; i < m ; i++)
			cin >> a[i] ;
		dp[0] = a[0] ;
		for(int j = 1 ; j < m ; j++)	{	
			if(dp[j-1] < 0)
				dp[j] = a[j] ;
			else
				dp[j] = dp[j-1]+a[j] ;
		}
			int max = dp[0] ;
			int y = 0  ;
			for(int k = 1 ; k < m ; k++)	
				if(dp[k] > max)	{
					max = dp[k] ;
					y = k ;
				}
			int s = 0 ;
			int x = y ;
			for( int l = y ; l >= 0 ; l-- )	{
				s += a[l] ;
				if( s == max )	{
					x = l ;
				}
			}
		 cout<<"Case "<<t++<<":"<<endl<<max<<" "<<x+1<<" "<<y+1<<endl;
        if(n) cout<<endl;
	}
	return 0 ;
}



	

HDU(1003)动态规划,布布扣,bubuko.com

HDU(1003)动态规划

原文：http://blog.csdn.net/ding_hai_long/article/details/20608783