【讲题】Galaxy OJ动态规划基础1——T1~T5

动态规划基础1

T1 滑雪

难度：普及-，做法：记忆化搜索

首先for一遍起点，分别使用dfs搜索，搜索过程记录答案，大大减少复杂度。

Code:

#include<bits/stdc++.h>
using namespace std;
int r,c,maxx=0,mx,my,dx[5]={-1,0,1,0},dy[5]={0,1,0,-1};
int a[110][110],dp[110][110],ans;
int dfs(int x,int y)
{
    if(dp[x][y])	return dp[x][y];
    int r=0;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(a[xx][yy]<a[x][y])
            r=max(r,dfs(xx,yy));
    }
    dp[x][y]=r+1;
    return ________;
}
int main()
{
    scanf("%d%d",&r,&c);
    memset(a,0x3f,sizeof(dp));
    for(int i=1;i<=r;i++)	
        for(int j=1;j<=c;j++)
        {
            scanf("%d",&a[i][j]);
            if(a[i][j]>maxx)
                mx=i,my=j,maxx=a[i][j];
        }
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            ans=max(ans,dfs(i,j));
    cout<<ans;
}

T2 最长下降子序列

难度：普及-，做法：动态规划

设 (dp_{i}) 为区间 ([1,i]) 中最长上升子序列的长度，不难得出状态转移方程为 (dp_j=max(dp_j, dp_i+1) (1 leq i leq n, 1 leq j < i, a_i<a_j)) 。

Code:

#include<bits/stdc++.h>
using namespace std;
int a[5001],dp[5001],n,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        dp[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]>a[i])
                dp[i]=max(dp[i],_____+1);
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}

T3 简单传纸条

难度：入门+，做法：你猜

很显然这题的做法是 ~~dfs~~ DP 。设 (dp_{i,j}) 为走到坐标 ((i,j)) 的最小八卦值之和。那么由于点 ((i,j)) 只能由点 ((i-1,j)) 或 ((i,j-1)) 到达，所以状态转移方程为 (dp_{i,j}=min(dp_{i-1,j},dp_{i,j-1}+a_{i,j}))。

Code:

#include <bits/stdc++.h>
using namespace std;
int n,m,a[2200][2200],dp[2200][2200];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    memset(dp,0x3f,sizeof(dp));
    dp[1][1]=a[1][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            dp[i][j]=min(dp[i][j],min(dp[i-1][j],dp[i][j-1])+_______);
    printf("%d",ans);
    return 0;
}

T4 数字三角形

难度：NOI/NOI+/CTSC，做法：~~膜你退火~~ 记忆化搜索

这是IOI 1994原题。
做法为从顶端的点开始向下dfs，回朔时记录下当前点的答案，以此避免 (O(2^n)) 的暴力搜索，时间复杂度变为 (O(n^2))。

Code:

#include <bits/stdc++.h>
using namespace std;
int n,a[2200][2200],dp[2200][2200];
int dfs(int dep,int x)
{
    if(dep>n || x>dep)  return 0;
    if(dp[dep][x])    return dp[dep][x];
    dp[dep][x]=max(dp[dep][x],dfs(dep+1,x));
    dp[dep][x]=max(dp[dep][x],dfs(dep+1,x+1));
    return dp[dep][x]+=_________;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
    printf("%d",dfs(1,1));
    return 0;
}

T5 递归函数

难度：普及-，做法：（伪）暴力

直接将递归公式原原本本抄下来，加上记忆化即可。
注：需要一定的玄学优化，不然会不明不白地TLE

Code:

#include<bits/stdc++.h>
using namespace std;
int a,b,c,ans,dp[60][60][60];
int w(int x,int y,int z)
{
    if(x<=0 || y<=0 || z<=0)
        return dp[0][0][0]=1;
    if(dp[x][y][z])
        return dp[x][y][z];
    if(x>20 || y>20 || z>20)
        return dp[x][y][z]=w(20,20,20);
    if(x<y && y<z)
        return dp[x][y][z]=w(x,y,z-1)+w(x,y-1,z-1)-w(x,y-1,z);
    return dp[x][y][z]=w(x-1,y,z)+w(x-1,y-1,z)+w(x-1,y,z-1)-w(x-1,y-1,z-1);
}
int main()
{
    while(true)
    {
        scanf("%d%d%d",&a,&b,&c);
        if(a==-1 && b==-1 && c==-1)
            break;
        if(a<=0 || b<=0 || c<=0)
            ans=1;
        else if(dp[a][b][c]==0)
            ans=w(a,b,c);
        else
            ans=dp[a][b][c];
        printf("w(%d, %d, %d) = %d
",_____,ans);
    }
    return 0;
}