比赛 201712练习 评测结果 AAAAAAAAAA
题目名称 硬币问题 最终得分 100
用户昵称 WHZ0325 运行时间 0.078 s
代码语言 C++ 内存使用 3.17 MiB
提交时间 2017-12-25 19:13:44
显示代码纯文本
#include <fstream>
using namespace std;
ifstream fin("kouka.in");
ofstream fout("kouka.out");
int n,s;
int v[150000];
int dx[150000],dn[150000];
int px[150000],pn[150000];
int main() {
	fin>>n>>s;
	for(int i=1;i<=n;i++) {
		fin>>v[i];
	}
	dx[0]=0;
	dn[0]=0;
	for(int i=1;i<=s;i++) {
		dx[i]=-(1<<30);
		dn[i]=1<<30;
	}
	for(int i=1;i<=s;i++) {
		for(int j=1;j<=n;j++) {
			if(i-v[j]>=0) {
				if(dx[i]<dx[i-v[j]]+1) {
					dx[i]=dx[i-v[j]]+1;
					px[i]=j;
				}
				if(dn[i]>dn[i-v[j]]+1) {
					dn[i]=dn[i-v[j]]+1;
					pn[i]=j;
				}
			}
		}
	}
	fout<<dn[s]<<" "<<dx[s]<<endl;
	int s0=s;
	while(s0) {
		fout<<pn[s0]<<" ";
		s0-=v[pn[s0]];
	}
	fout<<endl;
	s0=s;
	while(s0) {
		fout<<px[s0]<<" ";
		s0-=v[px[s0]];
	}
	fout<<endl;
	fin.close();
	fout.close();
	return 0;
}