ABC063 C Bugged
ABC063 C Bugged
問題概要
リンク参照
考察1
- 合計が10の倍数でない→合計値が答え
- そうでない場合→合計値から10の倍数でない最小の整数を引いたものが最大
考察2
- dp[i]:=整数iを作れるか(作れる場合は1)とし,dp[0]=1で初期化
- dp[j]==1の場合はdp[j + A[i]]=1と遷移できる(配列外参照に注意)
- 最終的に答えはループで回して10の倍数でなく,かつフラグの立っているものの中で最大のものとなる
ソースコード(考察1)
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> using namespace std; /******************************************************************************************/ int main() { int n; cin >> n; vector<int> a(n); int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } sort(a.begin(), a.end()); if ((sum % 10) != 0) { cout << sum << endl; return 0; } for (int i = 0; i < n; i++) { if (a[i] % 10) { cout << sum - a[i] << endl; return 0; } } cout << "0" << endl; return 0; }
ソースコード(考察2)
#include<iostream> #include<vector> #include<algorithm> #include<cctype> #include<utility> #include<string> #include<cmath> #include<cstring> #include<queue> #include<map> #include<set> #include<climits> #include<bitset> #include<stack> using namespace std; int dp[10005]; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } dp[0] = 1; for (int i = 0; i < N; i++) { for (int j = 10000; j >= 0; j--) { if (dp[j] == 0)continue; if (j + A[i] <= 10000) { dp[j + A[i]] = 1; } } } int maxi = 0; for (int i = 0; i <= 10000; i++) { if (dp[i] == 1 && ((i % 10) != 0)) { maxi = max(maxi, i); } } cout << maxi << endl; }