洛谷 P1077 题解

一、题意简述

这道题要使用 DFS 来解题。

Q:DFS 有哪些参数？

A:

1、花摆到了第几种？

2、摆了多少盆花？

二、求什么？

求方案总数

三、深搜的步骤：

1、查看是否应该终止 (花摆的盆数≥m)
2、递归所有可能的方案 (0~$a[i]$)

(若要记忆化搜索，只用加上提前 return 记忆的答案或 0 部分和存储部分即可)

三、复杂度
普通 DFS(30 分)
时间复杂度:O($a_1✕a_2✕ \cdots ✕a_n$)
空间复杂度:S($n$)

记忆化搜索 DFS(100 分)
时间复杂度:O($n$✕$m$✕$a_i$)
空间复杂度:S($n^2$)

四、代码

30分:

#include <bits/stdc++.h>
using namespace std;
int n,m,a[105],ans = 0;
void dfs(int i,int sum){
	if(sum == m){
		ans = (ans + 1) % 1000007;
		return ;
	}else if(sum > m){
		return ;
	}
	if(i > n)return ;
	for(int j = 0;j <= a[i];j++){
		dfs(i + 1,sum + j);
		if(sum + j > m)break;
	}
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int j = 1;j <= n;j++)scanf("%d",&a[j]);
	dfs(1,0);
	printf("%d",ans % 1000007);
	return 0;
}

100分:

#include <bits/stdc++.h>
using namespace std;
int n,m,a[105],form[105][105];
int dfs(int i,int sum){
    if(sum == m)return 1;
    if(sum > m)return 0;
    if(i > n)return 0;
    if(form[i][sum] != 0)return form[i][sum];
    int ans = 0;
    for(int j = 0;j <= a[i];j++)ans = (ans + dfs(i + 1,sum + j)) % 1000007;
form[i][sum] = ans;
return ans;
}
int main(){
memset(a,0,sizeof(a));
memset(form,0,sizeof(form));
    scanf("%d%d",&n,&m);
    for(int j = 1;j <= n;j++)scanf("%d",&a[j]);
    printf("%d",dfs(1,0) % 1000007);
    return 0;
}

浏览次数: