NEUQ-ACM预备队week8-创新互联

NEUQ-ACM预备队week8 1.疯狂的采药(P1616)(完全背包模板题)

一定要开long long,数据有坑(java是long)

为贵州等地区用户提供了全套网页设计制作服务,及贵州网站建设行业解决方案。主营业务为网站建设、成都网站制作、贵州网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

讲解可以看另一篇完全背包讲解

和一维01背包

import java.util.Scanner;

public class Main {public static void main(String[] args) {Scanner sc =new Scanner(System.in);
        long bagWeight = sc.nextInt();
        long n=sc.nextInt();
        long[] weight = new long[10005];
        int flag=0;
        long[] value = new long[10005];
        while (sc.hasNext()){weight[flag]=sc.nextInt();
            value[flag]=sc.nextInt();
            flag++;
        }
        if(n==1) System.out.println((bagWeight/weight[0])*value[0]);
        else{long[] dp = new long[(int) (bagWeight+1)];
            for (int i = 0; i< n; i++){// 遍历物品
                for (int j = (int) weight[i]; j<= bagWeight; j++){// 遍历背包容量
                    dp[j] = Math.max(dp[j], dp[(int) (j - weight[i])] + value[i]);
                }
            }
            System.out.println(dp[(int) bagWeight]);
        }}
}
2.樱花(P1833)(混合背包)

这个用java太麻烦了www,难搞哦

  • dp[j]表示消耗了j分钟最多可以有多少美学值,a[i]表示第i朵花最多可以看多少次
  • 当a[i]=0时,用完全背包
  • 其他时候用多重背包(01可以算是只能一次的多重背包)
#includeusing namespace std;
int c[100001],a[1000001],t[1000001],te1,te2,ts1,ts2,n,tz;//c[],t[]为题目等于,a[]表示最多看的次数,te1小时1,te2分钟1,ts1小时2,ts2分钟2,tz总时间
int dp[1001];//dp[j]表示消耗了j分钟最多可以有多少美学值
char cc;//符号':'
int main()
{
	cin>>te1>>cc>>te2>>ts1>>cc>>ts2;
	tz=60*(ts1-te1)+ts2-te2;
	cin>>n;
	for(int p=1;p<=n;p++) scanf("%d%d%d",&t[p],&c[p],&a[p]);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0){
			for(int j=t[i];j<=tz;j++) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
		}
		else{
		    for(int l=1;l<=a[i];l++)
		    for(int j=tz;j>=l*t[i];j--) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
		}
	}
	cout<
3.摆花(P1077)(01背包)

压成一维01背包

import java.util.Scanner;

public class Main {public static void main(String[] args) {int n,m,mod=1000007;
        int[] a=new int[105];
        int[] dp=new int[105];
        Scanner sc= new Scanner(System.in);
        n=sc.nextInt();
        m=sc.nextInt();
        for (int i = 1; i<=n ; i++) {a[i]=sc.nextInt();
        }
        dp[0]=1;
        for (int i = 1; i<=n ; i++) {for (int j = m; j >=0 ; j--) {for (int k = 1; k<=Math.min(a[i],j) ; k++) {dp[j]=(dp[j]+dp[j-k])%mod;
                }
            }
        }
        System.out.println(dp[m]);
    }
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


新闻标题:NEUQ-ACM预备队week8-创新互联
本文地址:http://myzitong.com/article/ppiig.html