路标

• • 题目描述
  • 解题思路
  • 代码

题目描述

题目传送门

解题思路

这题标签是dp，但实际上可以用搜索做，只需要用记忆化优化一下就行了（具体代码会有注释）

代码

#include<iostream>
#include<cstdio>
using namespace std;
int a[1001],f[1001][50],n,m;
int mod=1000007;
int dfs(int x,int k){//x表示当前搜到第几种花，k表示当前拿了多少盆花
	if(k>m) return 0;
	if(k==m) return 1;
	if(x>n) return 0;
	if(f[x][k]) return f[x][k];//如果搜索过了就返回
	int ans=0;
	for(int i=0;i<=a[x];i++) //枚举拿多少盆花
		ans=(ans+dfs(x+1,k+i))%mod;//枚举第x+1种花，k加上拿走的数量
	f[x][k]=ans;//记忆化
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cout<<dfs(1,0);
	return 0;
}

就是搜索的时间好像不太稳定。。