Wikioi 2144分銅秤量

713 ワード
アナログ
使用するテクニックは、前n/2個と後n/2個の分銅に分けることです
前n/2個の分銅で計測できる重量と使用する分銅の数を先に算出する(暴力計算)
mapに存在する
処理後n/2個の分銅の場合はm-現在の重量が可能かどうかを直接判断しansを更新すればよい
#include
#include
using namespace std;
map hash;
int a[50],n,m;
int ans=50;
void dfs1(int k,long long w,int num)
{
	if(w>m||k>n/2+1) return;
	hash[w]=(hash[w]>num||hash[w]==0)?num:hash[w];
	dfs1(k+1,w+a[k],num+1);
	dfs1(k+1,w,num);
}
void dfs2(int k,long long w,int num)
{
	if(w>m||k>n+1) return;
	if(w==m && ans>num) ans=num; 
	ans=(hash[m-w]!=0&&hash[m-w]+num
Jzoj 5425数論
Android原生とH 5のインタラクションの実現