AcWing 1020. 潜水员    原题链接    简单

作者： 作者的头像   Pr ,  2020-06-19 15:32:30 ,  所有人可见 ,  阅读 763

5


3

ac5d9f92f68db2d2b0abf1342569cf9cf24991e8.gif

坑点

1.某些负数状态可以转移
2.一些边界情况合法，另一些非法，非法的情况要初始化为不影响转移的值

图解

1.3.png

上代码

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
int f[N];
int n,m;
int main()
{
    cin>>n>>m;
    f[0]=1;
    for(int i=0;i<n;i++)
    {
        int w;
        scanf("%d",&w);
        for(int j=m;j>=w;j--)
        f[j]=f[j]+f[j-w];
    }
    cout<<f[m]<<endl;
    return 0;
}

2 评论

用户头像
LKW121   2021-08-03 21:09         踩      回复

动图好评

用户头像
滘   2020-09-04 11:37         踩      回复

大佬我这里哪里错了，救救孩子吧
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int O=input.nextInt();
int N=input.nextInt();
int K=input.nextInt();

    int []oo=new int[K+1];
    int []nn=new int[K+1];
    int [][][]dp=new int[K+1][O+1][N+1];
    int []arr=new int[K+1];

    for(int i=1;i<=K;i++)
    {

        oo[i]=input.nextInt();//O
        nn[i]=input.nextInt();//N
        arr[i]=input.nextInt();
    }

    for(int j=1;j<=O;j++)
    for(int k=1;k<=N;k++){
        dp[0][j][k]=Integer.MAX_VALUE;
    }
    // for(int i=1;i<=K;i++){
    //     dp[i][0][0]=0;
    // }
    dp[0][0][0]=0;
    for(int i=1;i<=K;i++){
        for(int j=1;j<=O;j++){
            for(int k=1;k<=N;k++){
                int t1=j-oo[i];
                int t2=k-nn[i];
                if(t1<0)t1=0;
                if(t2<0)t2=0;
                dp[i][j][k]=Math.min(dp[i-1][t1][t2]+arr[i],dp[i-1][j][k]);

            }
        }
    }
    System.out.println(dp[K][O][N]);
}

}