PKU 1010-STAMPS

問題概要

1010 STAMPS - PKU Wiki*
切手の数が25以下というわけではないみたい．

解法

全探索．

実装(Java)

import java.util.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {
	Scanner input;
	int n;//切手の種類
	int[] value=new int[1000];

	int ans_count=0;
	int ans_kind=-1;
	int ans_max=-1;
	int[] answer=new int[26];

	int[] now=new int[26];
	Boolean tie=false;
	void dfs(int depth,int v,int next){
		if(v==0){
			int kind=depth;
			int mv=-1;
			for(int i=0;i<depth;i++){
				for(int j=0;j<i;j++){
					if(now[i]==now[j]){
						kind--;
						break;
					}
				}
				mv=max(mv,now[i]);
			}
			if(kind>ans_kind||(kind==ans_kind&&ans_count>depth)||(kind==ans_kind&&ans_count==depth&&ans_max<mv)){
				for(int i=0;i<depth;i++){
					answer[i]=now[i];
				}
				ans_count=depth;
				ans_kind=kind;
				ans_max=mv;
				tie=false;
			}else if(kind>ans_kind||(kind==ans_kind&&ans_count>depth)||(kind==ans_kind&&ans_count==depth&&ans_max==mv)){
				tie=true;
			}
		}
		if(depth==4)return;
		if(v<0)return;
		for(int i=next;i<n;i++){
			now[depth]=i;
			dfs(depth+1,v-value[i],i);
		}
	}

	void run(){
		input=new Scanner(System.in);
		for(;input.hasNext();){
			n=0;
			for(n=0;input.hasNext();){
				int t=input.nextInt();
				if(t==0)break;
				value[n++]=t;
			}
			while(true){
				int t=input.nextInt();
				if(t==0)break;
				ans_count=-1;ans_kind=ans_max=-1;tie=false;
				dfs(0,t,0);
				if(ans_count==-1){
					printf("%d ---- none\n",t);
				}else if(tie){
					printf("%d (%d): tie\n",t,ans_kind);
				}else{
					printf("%d (%d):",t,ans_kind);
					for(int i=0;i<ans_count;i++){
						printf(" %d",value[answer[i]]);
					}
					printf("\n");
				}
			}
		}
	}

	void printf(String format,Object... args){
		System.out.printf(format, args);
	}

	public static void main(String[] args) {
		new Main().run();
	}

}