SW练习_P1077 摆花_DP

动态规划的题目，一般都比较绕弯弯

package info.frady.luogu;import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P1077 {static int N;static int M;static int[] arr;static int mod = 1000007;public static void main(String[] args) throws Exception{BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));StringTokenizer st=new StringTokenizer(reader.readLine());N=Integer.parseInt(st.nextToken());// 花的种类M=Integer.parseInt(st.nextToken());// 花的总数arr=new int[N+1];st=new StringTokenizer(reader.readLine());for (int i = 1; i <=N ; i++) {arr[i]=Integer.parseInt(st.nextToken());//每一种花的最多排放盆数}int[][] r=new int[N+1][M+1];// 花的种类  花的合计数r[0][0]=1;for (int i = 1; i <=N ; i++) {for (int j = 0; j <=M ; j++) {int v=Math.min(j,arr[i]);//每种花能摆放的最大= 此类花的最多限制, 最多摆放M盆  中最小的for (int k = 0; k <=v ; k++) {//此处合计的是 这种类型的花，可以摆放的每一种数量r[i][j]=(r[i][j]+r[i-1][j-k])%mod;}}}System.out.println(r[N][M]);reader.close();}
}