[数据结构与算法]hdu 2182 动态规划

前言

又是努力AC的一天

一、题目

传送门

二、代码

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[105][105] = {0};//dp[i][j]表示在进行了i次jump后落在j格时吃掉的虫子数 
int s[105];
int n, a, b, k;

int main() {
	int t;
	cin>>t;
	while(t--) {
		cin>>n>>a>>b>>k;
		memset(dp,0,sizeof(dp));
		for(int i=0; i<n; i++) {
			cin>>s[i];
		}
		dp[0][0]=s[0];//初始化，frog就在第一个格子里，所以虫子数=s[0] 
		int m=s[0];//记录最大值 
		for(int i=1; i*a<n&&i<=k; i++) {//第一层循环表示次数，次数范围要求小于k
		                                //并且如果每次跳a长，次数不能超过n/a; 
			for(int j=a; j<n&&j<=i*b; j++) {//第二层循环表示落脚的格数，小于n
			                                //并且要小于跳b(最大长度)长i次时的格数; 
				for(int k=j-b; k<=j-a; k++) {//循环遍历从当前位置找前一次跳跃吃到
				                             //虫子最多的那个位置 
					dp[i][j]=max(dp[i][j],dp[i-1][k]);
				}
				dp[i][j]+=s[j];//加上本格的虫子数 
				m=max(m,dp[i][j]);//取最大 
			}
		}
		cout<<m<<endl;
	}
}