結果
問題 |
No.27 板の準備
|
ユーザー |
![]() |
提出日時 | 2017-05-03 08:30:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 705 ms |
コンパイル使用メモリ | 48,640 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 13:00:15 |
合計ジャッジ時間 | 1,615 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include<cstdio> #include<vector> #include<algorithm> using namespace std; int min_u(int& m, int v) { if(m>v) { m=v; return 1; } return 0; } int main(void) { vector<vector<int> > dp(4); vector<int> v(4); int p, i, j, k, n, m; int minimum; for(i=0;i<dp.size();i++) dp[i].resize(30+1); while(scanf("%d%d%d%d", &v[0], &v[1], &v[2], &v[3])==4) { sort(v.begin(), v.end()); p=-1; k=0; for(int x: v) { if(p!=x) k++; p=x; } if(k<=3) { printf("4\n"); continue; } minimum=120; for(i=1;i<=v[0];i++) { fill(dp[0].begin(), dp[0].end(), 120); dp[0][0]=0; for(n=0;i*n<=30;n++) dp[0][i*n]=n; for(j=i+1;j<=v[2];j++) { dp[1]=dp[0]; for(m=0;m+j<=30;m++) { for(n=0;j*n+m<=30;n++) min_u(dp[1][j*n+m], dp[0][m]+n); } for(k=j+1;k<=v[3];k++) { dp[2]=dp[1]; for(m=0;m+j<=30;m++) { for(n=0;k*n+m<=30;n++) min_u(dp[2][k*n+m], dp[1][m]+n); } if(min_u(minimum, dp[2][v[0]]+dp[2][v[1]]+dp[2][v[2]]+dp[2][v[3]])) { /* printf("v %d %d %d %d\n", v[0], v[1], v[2], v[3]); printf("k %d %d %d\n", i, j, k); printf("n %d %d %d %d\n", dp[2][v[0]], dp[2][v[1]], dp[2][v[2]], dp[2][v[3]]); */ } } } } printf("%d\n", minimum); } return 0; }