暑假DP动态规划练习

1.https://cn.vjudge.net/problem/12304/origin    

从上往下走或者右下走找最大总和，也可以不同dp写。

注意动态规划这一步一定是和上一步或下一步有关联的

//dp[i][j]表示走到i，j这步时的最大值
for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+map[i][j];//（i，j）这一步是从（i-1，j）或者（i-1，j-1）走过来的
            ans=max(ans,dp[i][j]);
        }
        
    }

全部代码

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
int n,map[1000][1000],dp[1000][1000];
int ans=0;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>map[i][j];
        }
    }
    int i,j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=i;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+map[i][j];
            ans=max(ans,dp[i][j]);
        }
        
    }
    cout<<ans;
}

2.https://cn.vjudge.net/problem/30465/origin    

这题是看一个数能用几个不同二次方幂的数和表示

首先来练习一下深搜把，这一开始我没想到还能用深搜，尽管不对，当然可慢啦啦啦啦

#include<stdio.h> 
#include<math.h>
#include<iostream>
using namespace std;
int ans;
long long p[50];
void dfs(int n,int last)
{
    if(n==0)
    {
        ans++;
        return;
    }
    for(int i=0;n-p[i]>=0;i++)
    {
        if(p[i]>=last)
            dfs(n-p[i],p[i]);
    }
}
int main()
{
    int n;
    for(int i=0;i<=49;i++)
    p[i]=pow(2,i);
    cin>>n;
    dfs(n,0);
    printf("%d",ans);
  
    return 0;
}

接下来是dp版的，不知道为啥，还是超时！！！！，但思想要学习下，看懂下面的那个dp更新表就欧克了

dp表假设只有1，然后添加2，然后添加4然后添加8，更新表

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
long long dp[1000001],p[30];
int main()
{
    int n;
    
    while(scanf("%d",&n)!=EOF)
    {
    memset(dp,0,sizeof(dp));
    p[0]=dp[0]=1;
    for(int i=1;i<=29;i++)
    {
        p[i]=p[i-1]<<1;
    }
    for(int i=0;i<=29;i++)
    {
        if(p[i]<=n)
        {
            for(int j=p[i];j<=n;j++)
            {
                dp[j]=(dp[j]+dp[j-p[i]])%1000000000;
            }
        }
    }
    /*dp 1 2 3 4 5 6 7//假设输入7
    1    1 1 1 1 1 1 1
    2      2 2 3 3 4 4
    4          4 4 6 6
    */
    cout<<dp[n]<<endl; 
    }
    
 } 
 

最后过的是这个，我他喵。。。

#include<iostream>
#include<string.h>
using namespace std;
long long a[1000001];
int main()
{
    int n;
    a[1]=1,a[2]=2;
    for(int i=3;i<1000001;i++)
    {
        a[i]=a[i-2]+a[i/2];
        a[i]%=1000000000;
    }
    cin>>n;
    cout<<a[n];
 } 

1.n为奇数，a[n]=a[n-1]
2.n为偶数：
（1）如果加数里含1，则一定至少有两个1，即对n-2的每一个加数式后面 +1+1，总类数为a[n-2]；
（2）如果加数里没有1，即对n/2的每一个加数式乘以2，总类数为a[n/2]；

3.https://cn.vjudge.net/problem/18264/origin    

题意有两棵树1，2，掉苹果，人一开始在1下，有指定的移动次数，给苹果下落，求最多接到的苹果数

首先想一想，跟平常的题有什么区别

1.人会移动，

2.苹果要判断是否要不移动接到，还是移动接到

3.移动的次数不像是背包问题里的背包容量越多越好，但和背包问题类似

for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0];//第i个苹果，j次移动的最好结果，判断一直不动的情况
        if(t[i]==1) dp[i][0]++;
        
        for(int j=1;j<=w;j++)
        {
            if(j%2+1==t[i]){//判断移动后的位置在哪，如果跟这次下落苹果的位置一样
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+1;//dp的关键，跟上次的东西有关联，接这个苹果我可以选择i-1个苹果移动相同的次数，然后不动接
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//也可以从另一个苹果树移动过来接
            }
            else
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
        }
    }

整体代码

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int t[1000];
int dp[1000][1000];
int main()
{
    int n,w;
    cin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
    }
    
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=dp[i-1][0];
        if(t[i]==1) dp[i][0]++;
        
        for(int j=1;j<=w;j++)
        {
            if(j%2+1==t[i]){
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+1;
            }
            else
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]);
        }
    }
    cout<<dp[n][w]<<endl;
 } 

4.https://cn.vjudge.net/problem/16276/origin    

给定时间段，每个时间段有工作效率，每个时间段都要休息，求最大工作量

1.首先想到的是要对这些时间段排序，根据结束时间

2.对他们进行动态规划，具体思想可以参考求一个序列的最大上升子序列

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
struct node{
    int s,e,ef;
    
}x[100000];
bool cmp(node a,node b){
    return a.e<b.e;
}
int dp[100000];
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    for(int i=1;i<=b;i++)
    {
        cin>>x[i].s>>x[i].e>>x[i].ef;
        x[i].e+=c;
    }
    sort(x+1,x+1+b,cmp);
    memset(dp,0,sizeof(dp));
    int ans=0;
    for(int i=1;i<=b;i++)
    {
        dp[i]=x[i].ef;
        for(int j=1;j<i;j++)
        {
            if(x[i].s>=x[j].e)
            {
                dp[i]=max(dp[i],dp[j]+x[i].ef);//判断选这个或者不选这个，根据工作量大小
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    
}