• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

互联网 diligentman 1周前 (10-16) 15次浏览

NOIP 2018 提高组 复赛 第一天 第二题 货币系统  money   完全背包的计数问题   AC代码+15分代码+30分代码

总目录详见:NOIP 提高组 复赛 试题 目录 信奥 历年

在线测评地址:https://www.luogu.com.cn/problem/P5020

本文提供了AC代码的写法,15分代码的写法,30分代码的写法。

1.AC代码的写法

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

 

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

样例模拟如下:

4 
3 19 10 6

排序
3 6 10 19

6=3+3,故6可去除,因其可被3生成。
19=10+3*3=19,故19可去除,因其可被10,3生成。

数组剩下元素
3 10
共2个元素,输出2.

样例模拟完成,发现是完全背包的计数问题,不过还是有些怵,靠着残存的记忆,加上跟踪中间生成的数据,很快编码成功,样例通过,提交AC.第一次独立变成成功完全背包的计数问题,没有参考任何资料,编码也很快。可喜可贺。

AC代码如下:

#include <cstdio>
#include <algorithm>
using namespace std;
int a[110];
int dp[110][25010];
int main(){
	int t,i,j,n,mx,k,cnt;
	scanf("%d",&t);
	while(t--){
		mx=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d",&a[i]),mx=max(mx,a[i]);
		sort(a+1,a+1+n);//自小到大
		for(i=1;i<=n;i++)
			for(j=1;j<=mx;j++)
				dp[i][j]=0;
		for(i=0;i<=n;i++)dp[i][0]=1;//注意,此处n从0开始,而不是从1开始
		for(i=1;i<=n;i++)//对这三重循环,担心会超时,看了看数据范围,觉得也就17-20的数据点没把握,故若拿80分,心态也很平和。没想到,提交AC
			for(j=1;j<=mx;j++)
				for(k=0;k<=j/a[i];k++)//注意,此处k从0开始,而不是从1开始
					dp[i][j]+=dp[i-1][j-k*a[i]];
		cnt=0;
		for(i=1;i<=n;i++)
			if(dp[i][a[i]]==1)cnt++;//a[i]只被生成过一次。
		printf("%dn",cnt);
	}
	return 0;
}

2.15分代码的写法

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

 15分代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
int a[110];
int main(){
	int t,i,j,n;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		sort(a+1,a+1+n);//自小到大排序
		if(a[2]%a[1]==0)printf("1n");//a[2]能整除a[1]
		else printf("2n");//a[2]不能整除a[1]
	}
	return 0;
}

3.30分代码的写法

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

NOIP 2018 提高组 复赛 第一天 第二题 货币系统 money 完全背包的计数问题 AC代码+15分代码+30分代码

30分代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
int a[110];
int main(){
	int t,i,j,n,cnt;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		sort(a+1,a+1+n);//自小到大排序
		if(n==2){
			if(a[2]%a[1]==0)printf("1n");//a[2]能整除a[1]
			else printf("2n");//a[2]不能整除a[1]
		}
		if(n==3){
			cnt=3;
			for(i=2;i<=n;i++)
				if(a[i]%a[1]==0)cnt--;
			if(cnt==1)printf("1n");//a[2]能整除a[1],a[3]能整除a[1]
			else if(cnt==2)printf("2n");//a[2]能整除a[1]或者a[3]能整除a[1]
			else if(cnt==3){
				if(a[3]%a[2]==0)printf("2n");//a[3]能整除a[2]
				else{
					for(i=1;i<=a[3]/a[1];i++){
						for(j=1;j<=a[3]/a[2];j++)
							if(i*a[1]+j*a[2]==a[3]){
								cnt--;
								break;
							}
						if(cnt==2)break;//a[3]=i*a[1]+j*a[2]	
					}
					printf("%dn",cnt);
				}
			}
		}
	}
	return 0;
}

 


喜欢 (0)