NC54255. 吃面包
描述
输入描述
第一行输入两个整数用空格隔开 n, m， 表示zzz通过透视眼镜发现面包内一共有 n 处存在奶油（这 n 出奶油各自独立，两两不相连），zzz再获得超过 m 点饱腹感就有撑死的风险。
接来下 n 行，每行一个整数 g，表示某个位置存在 g 克奶油（如果zzz一旦选择某个位置开始吸奶油，则一定会吸完）。
0 ＜ n, m, g ≤ 1000
输出描述
输出一个整数，表示方案数对 109 + 7 取模的结果。
示例1
输入:
4 5 1 2 3 5
输出:
2
说明:
zzz可以吃第二个位置和第三个位置的奶油获得5点饱腹感，也可以只吃第四个位置获得5点饱腹感，所以一共有两种方案。Java(javac 1.8) 解法, 执行用时: 183ms, 内存消耗: 18212K, 提交时间: 2019-10-24 18:04:12
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int weight=in.nextInt(); //容量
int val[]=new int[n+1]; //背包
int dp[][]=new int[weight+1][n+1];
dp[0][0]=1;
Arrays.fill(dp[0],1);
for(int i=1;i<val.length;i++) {
val[i]=in.nextInt();
}
for(int i=1;i<=weight;i++) {
for(int j=1;j<val.length;j++) {
if(i>=val[j]) {
dp[i][j]=(int) ((dp[i][j-1]+dp[i-val[j]][j-1])%(1e9+7));
}
else {
dp[i][j]=dp[i][j-1];
}
}
}
// for(int i=0;i<dp.length;i++) {
// for(int j=0;j<dp[0].length;j++) {
// System.out.print(dp[i][j]+" ");
// }
// System.out.println();
// }
System.out.println(dp[weight][n]);
}
}
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 488K, 提交时间: 2020-10-18 23:23:16
#include<bits/stdc++.h>
const int mod=1e9+7;
using namespace std;
int N[1010];
int main(){
int n,m;
N[0]=1;
cin>>n>>m;
while(n--){
int v;
scanf("%d",&v);
for(int i=m;i>=v;i--){
N[i]=(N[i]+N[i-v])%mod;
}
}
cout<<N[m]<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 504K, 提交时间: 2019-10-24 19:55:42
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int mod=1000000007;
int a[1005],f;
int n,m;
int main(){
cin>>n>>m;
a[0]=1;
for(int i=0;i<n;i++){
cin>>f;
for(int i=m;i>=f;i--){
a[i]=(a[i]+a[i-f])%mod;
}
}
cout<<a[m];
return 0;
}