这是好久好久好久好久好久之前写的文章了(19年4月最后更新)然后我不知道干啥去了,就忘记发布了...
今天我看草稿箱,这文章都写得差不多了,竟然没发布,鸽了快一年(咕咕咕)
@

poj 1163 The Triangle

数字三角形,初学DP都是从本题开始做起的。
这类题其实有固定的套路,先开一个dp数组记录走到(i,j)位置时的数字之和。
第一步,令起点处的dp值等于a值。
第二步,从起点开始向终点递推(跳过起点),走到(i,j)时,根据题目找到上一步的最大dp值加上此时的a值,得到dp[i][j],也就是所谓的确定状态转移方程。(本题是dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]
第三步,找最大的dp值,它可能就是终点的dp值,或者是dp数组中最后一行的最大值。

#include <iostream>
using namespace std;
int n,mx,a[110][110],dp[110][110];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
            if(i==1&&j==1){dp[i][j]=a[i][j];continue;}//(1,1)处的dp值就等于a的值
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];
            //其他位置的dp值是上一状态dp的最大值加上此时的a值
        }
    for(int i=1;i<=n;i++)//寻找最后一行的最大dp值
        mx=max(mx,dp[n][i]);
    cout<<mx<<endl;
    return 0;
}

poj 1088 滑雪

记忆化搜索。(其实就是算法书上的备忘录算法,把搜索过的值记下来,下次再遇见就不再搜索了)

#include <cstdio>
#include <iostream>
using namespace std;
const int N=110;
int n,m,ans,a[N][N],dp[N][N];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
int dfs(int x,int y)
{
    if(dp[x][y])return dp[x][y];//被搜索过
    int mx=1;//至少长度为1(自己本身)
    for(int i=0;i<4;i++)
    {
        int nx=x+dir[i][0];
        int ny=y+dir[i][1];
        if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]<a[x][y])
            mx=max(mx,dfs(nx,ny)+1);
    }
    dp[x][y]=mx;
    return mx;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans=max(ans,dfs(i,j));
    printf("%d\n",ans);
    return 0;
}

hdu 1003 Max Sum

这题的意思应该是找最大子段和,“第一个区间”的意思是优先L小的,如果L相同,优先R小的。

思路就是如果加起来的数大于等于0,就一直加a[i],否则就重新开始加并且更新左端点。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int T,n,ansl,ansr,a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>T;
    for(int cas=1;cas<=T;cas++)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        int tmp=0,l=1,mx=-2e9;
        for(int i=1;i<=n;i++)
        {
            if(tmp>=0)tmp+=a[i];
            else l=i,tmp=a[i];
            if(tmp>mx)
            {
                mx=tmp;
                ansl=l;
                ansr=i;
            }
        }
        printf("Case %d:\n",cas);
        printf("%d %d %d\n",mx,ansl,ansr);
        if(cas<T)printf("\n");
    }
    return 0;
}

poj 2533 Longest Ordered Subsequence

求最长上升子序列,子序列可以不连续。

O(n^2^)算法:

#include <iostream>
using namespace std;
int a[1005],dp[1005];//dp[i]表示在a[1]~a[i]之间最长上升序列的长度
int main()
{
    int n,mx;
    cin>>n;
    for(int i=1;i<=n;i++)
    {cin>>a[i];dp[i]=1;}//初始化dp[i]为1
    mx=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {if(a[j]<a[i])dp[i]=max(dp[j]+1,dp[i]);}
        //若a[i]能接在a[j]之后构成上升序列且接上后是新的最长序列,则更新dp[i]
        mx=max(dp[i],mx);//在dp[1]~dp[n]内求出最大的dp[i]即为答案
    }
    cout<<mx<<endl;
    return 0;
}

O(nlogn)算法:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n,num[N],l[N],dp[N],cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>num[i];
    cnt=0;
    l[cnt]=-1; // 这里初始化容易错,如果默认初始化为0,而且答案子序列的第一个是0,则不会计入
    for(int i=0;i<n;i++)
    {
        if(num[i]>l[cnt])
        {
            l[++cnt]=num[i];
            dp[i]=cnt;
        }
        else
        {
            int k=lower_bound(l,l+cnt,num[i])-l;
            l[k]=num[i];
            dp[i]=k;
        }
    }
    int ans=1;
    for(int i=0;i<n;i++)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}
/*
9
0 5 10 50 100 500 1000 5000 10000
ans:9
*/

nefu 1727 登山-DP

两个相反的最长上升子序列的长度dp之和。

#include <bits/stdc++.h>
using namespace std;
int n,cnt,ans,a[1010],b[1010],dp1[1010],dp2[1010];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        dp1[i]=dp2[i]=1;
    }
    cnt=0;
    for(int i=n;i>=1;i--)
        b[++cnt]=a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i-1;j++)
        {
            if(a[j]<a[i])dp1[i]=max(dp1[j]+1,dp1[i]);
            if(b[j]<b[i])dp2[i]=max(dp2[j]+1,dp2[i]);
        }
    }
    ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,dp1[i]+dp2[n-i+1]-1);
    printf("%d\n",ans);
    return 0;
}

hdu 2571 命运

本题走到(i,j)时,上一步的dp最大值可能出现在三个位置:左边一格、上边一格、或者第i行第k列(k为j的因子,即k乘以一个数等于j)。

注意要把dp初始化为负数,因为a中出现了负值。

注意要特判dp[1][1],不能让dp[1][1]=max(dp[0][1],dp[1][0]),否则dp[1][1]变成inf。

#include <bits/stdc++.h>
#define max3(a,b,c) max(max(a,b),c)//定义三个数的最大值
using namespace std;
const int inf=-0x3f3f3f3f;
int t,n,m,mx,a[30][1010],dp[30][1010];
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(dp,inf,sizeof(dp));//dp要初始化为负数,包括第0行和第0列的所有元素
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>a[i][j];
        dp[1][1]=a[1][1];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                mx=inf;//mx表示上一状态的最大dp值,mx初始化不要放在一层循环的外面,注意细节
                if(i==1&&j==1)continue;//防止dp[1][1]=max(dp[0][1],dp[1][0])
                for(int k=1;k<=j-1;k++)
                {if(j%k==0)mx=max(mx,dp[i][k]);}
                mx=max3(mx,dp[i-1][j],dp[i][j-1]);
                dp[i][j]=a[i][j]+mx;
            }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

hdu 1176 免费馅饼

这题要自己构造一个二维矩阵,0~ 10列,1~maxt行(maxt为最大时间),在t时刻的x位置掉了馅饼,则把a[t][x]++,统计完所有a[t][x]位置掉的馅饼数之后,dp数组从最后一行也就是第maxt行从下往上递推,递推到(0,5)这个位置,也就是第0秒所在的起点位置5,递推得到的dp[0][5]即为答案。

#include <bits/stdc++.h>
#define max3(a,b,c) max(max(a,b),c)//定义三个数的最大值
using namespace std;
int n,x,t,maxt,a[100010][20],dp[100010][20];
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        memset(a,0,sizeof(a));
        memset(dp,0,sizeof(dp));
        maxt=0;
        while(n--)
        {
            cin>>x>>t;
            maxt=max(maxt,t);//maxt为最大的时间
            a[t][x]++;
        }
        for(int i=0;i<=10;i++)
            dp[maxt][i]=a[maxt][i];//先初始化最后一行的dp数值
        for(int i=maxt-1;i>=0;i--)
            for(int j=0;j<=10;j++)
            {
                if(j==0)dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];//第0列不能向左走,不能j-1
                else dp[i][j]=max3(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])+a[i][j];
            }
        printf("%d\n",dp[0][5]);
    }
    return 0;
}

更新一个题:最大子矩阵【前缀和+一维最大字段和】

NEFU 1728 最大子矩阵-DP

先写两重循环枚举起点行k1到终点行k2,再写一个循环遍历每列i,将列i压缩成一个数字,它表示第i列k1~k2行的前缀和(用二维前缀和预处理),那么就变成了一个1*n的矩阵,即一个一维数组,然后求其最大子段和,同时取max即可。

时间复杂度O(n^3)。

#include <bits/stdc++.h>
using namespace std;
const int N=510,inf=1e18;
typedef long long ll;
ll a[N][N],sum[N][N],dp[N];
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+a[i][j]; // 第j列前i行的前缀和
        }
    }
    ll mx=-inf;
    for(int k1=1;k1<=n;k1++) // 行 上端点
    {
        for(int k2=k1;k2<=n;k2++) // 行 下端点
        {
            //dp[0]=0;
            for(int i=1;i<=n;i++) // 列
            {
                ll tmp=sum[k2][i]-sum[k1-1][i]; // 第i列 [k1,k2]行之和
                dp[i]=max(dp[i-1]+tmp,tmp); // 最大子段和求法
                mx=max(mx,dp[i]);
            }
        }
    }
    printf("%lld\n",mx);
    return 0;
}
/*
3
-1 -4 3
3 4 -1
-5 -2 8
ans:10

4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2
ans:15
*/