第一篇题解中为什么变成一维之后那个k要从1开始呢?
查看原帖
第一篇题解中为什么变成一维之后那个k要从1开始呢?
420731
baizhiheizi楼主2021/7/28 17:11

方法五当中的背包那个思路,我自己想的时候,只改了j的范围,然后全wa了,当改成1就过了,这是什么原因呢?

#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000007;
typedef long long ll;
int n,m,a[105];
int dp[105];
int ans=-1;

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=0;j--){
			for(int k=1;k<=min(j,a[i]);k++){
				//这种花最多放几盆 
				dp[j]=(dp[j]+dp[j-k])%mod;
			}	
		}
	}
	cout<<dp[m]<<endl;
	return 0;
}
2021/7/28 17:11
加载中...