はやし屋

競技プログラミングのメモ きたない

PCK 2013 本選 4,6

ウッ頭が...

巨樹の刻み手
再帰でやると無限にやる場合の場合わけとかめんどくさそう

dpる

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

#define ALL(a) a.begin() , a.end()
#define chmin(a,b) a=min(a,b)

int main(){
  int d , n;
  while(cin >> d >> n && (d|n)){
    int a[111] , e[111] , r[111]; 
    for(int i = 0 ; i < n ; ++i){
      cin >> a[i] >> e[i] >> r[i];
    }
    vector < vector < int > > dp(111,vector < int >(111,1<<28));
    dp[d][0] = 0;
    for(int D = d ; D > 0 ; --D){
      for(int E = 0 ; E <= 100 ; ++E){
	if(dp[D][E] != 1<<28){
	  for(int i = 0 ; i < n ; ++i){
	    if(E >= r[i]){
	      chmin(dp[max(D-a[i],0)][min(100,E+e[i])],dp[D][E]+1);
	    }
	  }
	}
      }
    }
    int ret = *min_element(ALL(dp[0]));
    if(ret == 1 << 28)cout << "NA" << endl;
    else cout << ret << endl;
  }
  return 0;
}


微生物発電
bitdpる
最初何もしなずidx+1する場合って無駄じゃねっと思ったが、
無駄じゃない場合があった(サンプル3)
forでやった方バグってしまった...

#include<iostream>
#include<map>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdlib>
using namespace std;

#define SQR(q) ((q)*(q))
#define add(a,b) (abs(a-(b)) * SQR(abs(a-(b))-30))

int n , w;
int bm[16] , bw[16];
int dp[1 << 16][16];

int solve(int idx, int bit){
  if(idx == n)return 0;
  if(~dp[bit][idx])return dp[bit][idx];
  int ret = solve(idx+1 , bit);
  for(int i = 0 ; i < w ; ++i){
    if(!((bit >> i)&1)){
      ret = max(ret,solve(idx+1 , bit | (1 << i))+add(bw[i],bm[idx]));
    }
  }
  return dp[bit][idx] = ret;
}

int main(){
  while(cin >> n >> w && (w|n)){
    for(int i = 0 ; i < n ; ++i)cin >> bm[i];
    for(int i = 0 ; i < w ; ++i)cin >> bw[i];
    memset(dp,-1,sizeof(dp));
    int ret = solve(0,0);
    cout << ret << endl;
  }
  return 0;
}