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 1 0 0 0 10 1 2 3 4 5 6
演示样例输出
15
卡了两天了。。倒是一看就是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 <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <vector> #include <queue> #include <set> #include <cmath> #include <map> #include <stack> #define ll long long using 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 ",ans); } return 0; }看了标程写的记忆化搜索，感觉记忆化也没那么神奇了，曾经从来没了解过QAQ。。我的理解是：找出状态数组，当你推不出来状态转移方程的时候，记忆化搜索也许不失为一种解决方式。前提是要有把搜索过程中的数据保存起来的思想，盲目的暴搜是不能解决这个问题的。。会T到没盆友的我深有体会。。#include <iostream> #include <cstdio> #include <algorithm> #include <set> #include <cctype> #include <cstring> #include <string> #include <vector> #include <stack> #include <queue> using namespace std; #define ll long long const 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<n;i++) tem=max(tem,dfs(i+s,k-1)); } dp[s][k]+=tem; return dp[s][k]; } int main() { while(scanf("%d%d",&n,&kk)!=EOF) { memset(dp,-1,sizeof(dp)); for(int i=0;i<n;i++) scanf("%d",a+i); ans=-INF; for(int i=0;i<n;i++) { ans=max(dfs(i,kk),ans); } printf("%d ",ans); } return 0; }
</pre><pre>