接着讲动态规划

目录

题目：尼克的任务

  思路：

题目：数楼梯

  思路： 

题目：小A点菜

  思路：

---

     

题目：尼克的任务

      

思路：

题意：当同一时刻有多个任务，尼克可以任选一个，其余则由同事完成，如果只有一个任务，则该任务必需由尼克做。

因为第i时刻的最大空闲时间是和后面i选择任务的持续时间的时刻有关系的，也就是说，如果要求从1~i的最大空闲时间，和之前1~j（j<i）没有转移关系。所以正着找肯定是不行的。我们可以尝试一下倒着dp，我们用f[i]表示i~n的最大空闲时间
当i时间没有任务时：f[i]=f[i+1]+1;
当i时间有任务时：f[i]=max(f[i],f[i+a[sum]])   (这样子就可以借助之前的结果dp了)
 

#include<iostream>   
#include<algorithm>  
using namespace std;  
long int n,k,sum[10001],num=1,f[10001];  
struct work//结构体，一起排序 ，从大到小   
{  
    long int ks,js;  
}z[10001];  
int cmp(work a,work b)  
{  
    return a.ks>b.ks;//我们倒着遍历任务就需要任务按开始时间降序排列
}  
int main()  
{  
    long int i,j;   
    cin>>n>>k;  
    for(i=1;i<=k;i++)  
    {  
    cin>>z[i].ks>>z[i].js;    
    sum[z[i].ks]++;  //对同一开始时间的任务统计
    }  
    sort(z+1,z+k+1,cmp);  
    for(i=n;i>=1;i--)//倒着搜   
    {  
        if(sum[i]==0) f[i]=f[i+1]+1;//此时没有开始的任务  
        else for(j=1;j<=sum[i];j++)  
        {  
            f[i]=max(f[i],f[i+z[num].js]);
            num++;//当前已扫过的任务数   
        }  
    }  
    cout<<f[1]<<endl;  
}  

   

   

---

   

题目：数楼梯

    

思路： 

思路很简单，就是正常的递推就行，但是一维的话，数据太大，会爆掉内存的，必须使用高精度才行。

#include <iostream>                                     //数楼梯  ，递推方式（动态规划）
using namespace std;
int n,len=1,f[5001][5001];
void stair(int k)
{  
	for(int i=1;i<=len;i++)                //相加过程
      f[k][i]=f[k-1][i]+f[k-2][i];
    for(int i=1;i<=len;i++)               //进位过程
      if(f[k][i]>=10)
      {	f[k][i+1]+=f[k][i]/10;
        f[k][i]=f[k][i]%10;
        if(f[k][len+1])len++;             //只要len+1不为0就len++，巧妙解决长度问题
	  }
}
int main()
{
	cin>>n;f[1][1]=1;f[2][1]=2;         //斐波那契数列初始化
	for(int i=3;i<=n;i++)
		stair(i);
	for(int i=len;i>=1;i--)cout<<f[n][i];            //高精相加，倒序输出，因为位数精确，所以无需消除前置0
	return 0;	
}

    

---

    

题目：小A点菜

   

 思路：

 题意：小A点菜，一共由n种菜，第i种为ai元，每种菜只有一个，求花光m元的方案

 设置状态：dp[i][j] 中，i表示遍历到了第i道菜，j表示已经化的钱，dp表示方案数

 递推式：dp[i][j]+=dp[i-1][j];  if(j>=a[i]) dp[i][j]+=dp[i-1][j-a[i]];

#include <iostream>                      
using namespace std;
int a[101],dp[101][10001];                 //i表示遍历到了第i道菜，j表示已经化的钱，dp表示方案数，求dp[n][m]即可              
int main()
{
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];         
	for(int i=0;i<=n;i++) //注意这里要从0开始 
      dp[i][0]=1;   
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=m;j++)
	  {  dp[i][j]+=dp[i-1][j];
	     if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];
//	  if(j==a[i])dp[i][j]=dp[i-1][j]+1;               //第i道菜吃，有1种，不吃，有的dp[i-1][j]种
//	  	 if(j>a[i])dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]];  //第i道菜吃有dp[i-1][j-a[i]],不吃有dp[i-1][j]种
//	  	 if(j<a[i])dp[i][j]=dp[i-1][j];                  //第i道菜不能吃，只能不吃
	  }
	  cout<<dp[n][m];
	  return 0;
}