首页 > 代码库 > 基础简单DP

基础简单DP

2024-10-24 12:37:01   210人阅读

状态比较容易表示，转移方程比较好想，问题比较基本常见   递推、背包、LIS（最长递增序列），LCS（最长公共子序列）

HDU 2048 数塔

由上往下推 状态数太多(100!) 可以由下往上推:

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j])

储存的话就直接一个二维数组a[110][110]

HDU2018 母牛

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

斐波那契数列 递推 线性递归

dp[i]=dp[i-1]+dp[i-3];

HDU2044 一只小蜜蜂

斐波那契数列 递推 线性递归

先发现 n(n>=3)可由n-1及n-2到达 所以递推得到到达n的方法是到达n-1的方法+到达n-2的方法

HDU2050 折线分割平面

①n条直线能把平面分成几部分: 2+2+3+4......递推公式 f(n)=f(n-1)+n

②一个圆与n条直线 这些直线中每一条在圆内同其他直线相交，假设没有3条直线相交于一点，试问这些直线将圆分成多少区域:

与①相同 

现在看下本题 平面的部分数与顶点即直线的交点有关 n=1时有2条线1个交点 部分为2 n=2时有3有4条线6个交点部分为7 所以n=n-1时有 2*(n-1)条线所以n=n时可增加2*2*(n-1)+1(本身的顶点)个部分

即递推公式为 f(n)=f(n-1)+4*(n-1)+1;

codeforces 429B B. Working out

先处理出从左上到右下的最大值和左下到右上的最大值然后枚举交点和进出的方向

技术分享 
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp1[1010][1010],dp2[1010][1010],dp3[1010][1010],dp4[1010][1010];
int ans[1010][1010];
//(1,1)->(i,j)+(i,j)->(n,m)+(n,1)->(i,j)+(i,j)->(1,m);
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&ans[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp1[i][j]=max(dp1[i-1][j],dp1[i][j-1])+ans[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            dp2[i][j]=max(dp2[i+1][j],dp2[i][j+1])+ans[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=1;j--){
            dp3[i][j]=max(dp3[i-1][j],dp3[i][j+1])+ans[i][j];
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=m;j++){
            dp4[i][j]=max(dp4[i][j-1],dp4[i+1][j])+ans[i][j];
        }
    }
    int cnt=0;
    for(int i=2;i<n;i++){
        for(int j=2;j<m;j++){
            cnt=max(cnt,dp1[i-1][j]+dp2[i+1][j]+dp3[i][j+1]+dp4[i][j-1]);
            cnt=max(cnt,dp1[i][j-1]+dp2[i][j+1]+dp3[i-1][j]+dp4[i+1][j]);
        }
    }
    printf("%d\n",cnt);
    return 0;
}
View Code

 

 

基础简单DP


联系
我们