还未理解动态规划。。。

hdu 1003 ：max sum
题意：
给出一个数组，计算这个数组中一段连续的数字的最大的和。
思路：
wa了无数次，是还没有理解动态规划吧。。。看了百度百科对于最大子段和的动态规划解法，才理解了一点。此题所求的是max（a[i] + a[i + 1] + ... + a[j],1 <= i <= j <= n）。由此可得转移方程是dp[j] = max(dp[j-1] + a[j],a[j])（为啥啊）。我的理解是如果说dp[j-1]已经小于0了的话，那么a[i]再加上一个小于0的数肯定会使得后面的和减小，所以就把当前的dp[i]置为a[i]。这道题很恼火的地方是记录最大值的开始位置和结束的位置。我使用的方法并不能准确的记录开始的位置，去看了一下discuss，居然有仁兄和我使用一样的方法，他记录开始位置是首先找出最大值和结束位置，利用这两个值去推出开始位置，真是让我叹服。另外还有一种不需要数组的方法，一并记录一下。
代码：mine

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int a[100005];
int dp[100005];
const int minn = -1e9 - 1;
int main()
{
    int t;
    scanf("%d",&t);
    for (int k = 1;k <= t;k++)
    {
        int n;
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        for (int i = 1;i <= n;i++){ dp[i] = minn;scanf("%d",&a[i]);}
        int st = 1,en = 1;
        int maxx = a[1];
        dp[1] = a[1];
        for (int i = 2;i <= n;i++)
        {
            if (dp[i-1] > 0) dp[i] = a[i] + dp[i-1];
            else 
            {
                dp[i] = a[i];
            }
            if (dp[i] > maxx)
            {
                maxx = dp[i];
                en = i;
            }
        }
        int sum = 0;
        for (int i = en;i >= 1;i--)
        {
            sum += a[i];
            if (sum == maxx)
            {
                st = i;
                break;
            }
        }
        printf("Case %d:\n%d %d %d\n",k,maxx,st,en);
        if (k != t) printf("\n");
    }
    return 0;
}

借鉴：

#include <stdio.h>
int main()
{
    int t;
    scanf("%d",&t);
    for (int k = 1;k <= t;k++)
    {
        int sum = 0,maxx = -1001;
        int tmp = 1,st = 1,en = 1;
        int n;
        scanf("%d",&n);
        for (int i  = 1;i <= n;i++)
        {
            int a;
            scanf("%d",&a);
            sum += a;
            if (sum > maxx)
            {
                maxx = sum;
                st = tmp;
                en = i;
            }
            if (sum < 0)
            {
                sum = 0;
                tmp = i + 1;
            }
        }
        printf("Case %d:\n%d %d %d\n",k,maxx,st,en);
        if (k != t) printf("\n");
    }
    return 0;
}

poj 1050:to the max
ps:n^4的复杂度居然a了，我也不知道说什么好。。。但是一次就a，真是一次就好啊。
题意：
给出一个矩阵，找出其中和最大的子矩阵的和。
思路：
枚举从哪一行开始，然后枚举横向长度为0到n-1，之后再一行一行向下扫描，不断更新最大值，最后输出最大值，其实dp数组也是完全没有必要的。这题是借鉴了最小子段和的思路。把一个方块看成一条线来处理的。
代码：

#include <stdio.h>
#include <string.h>
int a[105][105];
int dp[105];
int sum(int f,int st,int len)
{
    int ans = 0;
    for (int i = 0; i < len;i++)
        ans += a[f][i+st];
    return ans;
}
int main()
{
    int n;
    int res = -300;
    memset(a,0,sizeof(a));
    memset(dp,0,sizeof(dp));
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            scanf("%d",&a[i][j]);
    for (int i = 1;i <= n;i++)
    {
        int maxx = -200;
        for (int len = 0;len + i <= n;len++)
        {
            int tmp = 0;
            for (int k = 0; k <= len;k++)
                tmp += a[1][i+k];
            for (int k = 2;k <= n;k++)
            {
                int tmp0 = sum(k,i,len);
                if (tmp < 0) tmp = tmp0;
                else tmp  = tmp0 + tmp;
                if (tmp > maxx) maxx = tmp;
            }
        }
        dp[i] = maxx;
        if (maxx > res) res = maxx;
    }
    printf("%d\n",res);
    return 0;
}

ps:有一种n^3的解法，mark一下，过一段时间用这个思路，写一下，提示：压缩矩阵。