結果
問題 | No.45 回転寿司 |
ユーザー |
|
提出日時 | 2017-03-09 23:44:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 814 bytes |
コンパイル時間 | 622 ms |
コンパイル使用メモリ | 72,124 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-27 16:11:26 |
合計ジャッジ時間 | 1,616 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include<iostream>#include<algorithm>#include<vector>using namespace std;//これも動的計画法で行けそう?const int INF = 99999999;vector<int> sushi;vector<int> umai(1001, INF);int dp(int index){if(index < 0) return 0;if(umai[index] != INF){return umai[index];}return umai[index] = max(dp(index-1), dp(index-2) + sushi[index]);}int main(){int n, tmp;cin >> n;for(int i=0; i<n; i++){cin >> tmp;sushi.push_back(tmp);}cout << dp(n) << endl;/*umai[0] = -100;for(int i=0; i<n; i++){for(int j=100000; j >=0 ; j--){if(umai[j] != INF){if(umai[j] != i-1) umai[j+sushi[i]] = i;}}}//for(int i=1; i<20 ; i++) cout << umai[i] <<endl;for(int i=100000; i>=0; i--) {if(umai[i] != INF){cout << i << endl;return 0;}}*/}