SDUT 2893-B（DP || 记忆化搜索）-白红宇

SDUT 2893-B（DP || 记忆化搜索）

阅读量：4625 次

发布时间：2019-06-09

本文共 1904 字，大约阅读时间需要 6 分钟。

B

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描写叙述

有n块地板排成一条直线，从左到右编号为1,2,3. . . n-1,n，每块地板上有一个权值w。如今要小B用这n块地板玩一个游戏。

小B能够选择随意一块地板作为起点，然后向右跳K次，每次最多能够跳5个格子(设起跳点地板编号为x，落地点为y，y-x <= 5)。每踩在一块地板上，小B的得分sum += wi

，小B每次仅仅能踩一块地板，開始时sum = 0。如今请你编写一个程序求最大的sum。

输入

多组输入.第一行输入两个整数n，k。(1<= n && n <= 100 ,1 <= k && k <= min(n,50))。

接下来n行，每行一个整数，依次表示Wi。(0 <= wi && wi <= 100)。

输出

每组数据输出一个整数，代表答案。

演示样例输入

10 10 0 0 10 1 2 3 4 5 6

演示样例输出

卡了两天了。。倒是一看就是dp可解，大体状态也表示好了，但死活没推出状态转移方程。看了一下标程，顿感自己萨比了。。

dp[i][j] 代表跳j次能够到达i处（i为数组下标） 可得

dp[i][j]=max(dp[i][j],dp[i-k][j-1])(k∈[1,min(i,5)]);注意边界。。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define ll long longusing namespace std;const int INF=0x3f3f3f3f;int n,k,a[110],dp[110][55];int main(){ while(scanf("%d%d",&n,&k)!=EOF) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); dp[i][0]=a[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=min(i,5);j++) { for(int tk=1;tk<=k;tk++) dp[i][tk]=max(dp[i][tk],dp[i-j][tk-1]+a[i]); } } int ans=-INF; for(int i=1;i<=n;i++) ans=max(ans,dp[i][k]); printf("%d\n",ans); } return 0;}

看了标程写的记忆化搜索，感觉记忆化也没那么神奇了，曾经从来没了解过QAQ。。我的理解是：找出状态数组，当你推不出来状态转移方程的时候，记忆化搜索也许不失为一种解决方式。前提是要有把搜索过程中的数据保存起来的思想，盲目的暴搜是不能解决这个问题的。。会T到没盆友的我深有体会。。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define ll long longconst int maxn=110;const int INF=0x3f3f3f3f;int a[maxn],n,kk,tem,ans;int dp[maxn][55];int dfs(int s,int k){ if(dp[s][k]!=-1) return dp[s][k]; dp[s][k]=a[s]; int tem=0; if(k) { for(int i=1;i<=5&&i+s

转载于:https://www.cnblogs.com/blfshiye/p/4294833.html

你可能感兴趣的文章

[Swift实际操作]七、常见概念-(2)点CGPoint和变形CGAffineTransform的使用