yukicoder No.27 板の準備
感想
制約が小さいので全探索できそう。
A,B,Cのそれぞれの長さ、それぞれの使う枚数について回して30^6ぐらいだけど実際はもう少し小さいから間に合った。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-8; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; int sub(int a,int b,int c,int n){ int ret = INF/2; for(int i=n/c;i>=0;i--){ for(int j=n/b;j>=0;j--){ for(int k=n/a;k>=0;k--){ if(c*i+b*j+a*k == n){ ret = min(ret,i+j+k); } } } } return ret; } int func(int a,int b,int c,vector<int>& v){ int ret = 0; for(int l=0;l<4;l++){ ret += sub(a,b,c,v[l]); } return ret; } int main(void) { vector<int> v(4); cin >> v[0] >> v[1] >> v[2] >> v[3]; sort(begin(v),end(v)); int ret = INF; for(int a=1;a<=30;a++){ for(int b=a+1;b<=30;b++){ for(int c=b+1;c<=30;c++){ ret = min(ret,func(a,b,c,v)); } } } cout << ret << endl; return 0; }
★3なのに全探索で通ってしまい不安。
DPで縮められるらしいので調べておきたい。