4. 幽邃魔窟
题目ID：20293必做题100分
最新提交：
Runtime Error
40 分
历史最高：
Wrong Answer
60 分
时间限制: 2000ms
空间限制: 262144kB
题目描述
整个大陆被分成了许多个部落，庆帝与弗里茨王为了争夺统治权，在每个部落都安置了士兵。士兵更多的一方将会掌管整个部落，收纳部落上的所有子民，最后拥有更多子民的首领会被全世界认可，享有至高无上的权力。
你是来自幽邃魔窟的女巫，拥有蛊惑人心的能力，庆帝请你帮助他蛊惑一部分弗里茨王的士兵，将他们转变为自己的士兵，从而能够夺取部分部落的统治权，收纳更多子民。而你表面看似帮助庆帝，实则内心怀揣着一个更加邪恶的计划。在帮助庆帝成为整个大陆唯一的王之后，你将蛊惑庆帝变为你的傀儡，并用他的权力操纵全世界的子民，蛊惑所有人成为你的奴隶，最后将幽邃魔窟的魔王传送到这个世界，控制整个大陆，肆虐一切生灵！！！！
当然，你得先帮助庆帝实现他的目标。蛊惑士兵需要花费一定的魔力，你希望蛊惑最少的士兵使一些部落中庆帝的士兵多于弗里茨王的士兵，这些部落的子民都归庆帝所有，最后庆帝的子民大于弗里茨王的子民。
具体的，整个大陆有 nn 个部落，其中第 ii 个部落中庆帝有 aiai 个士兵，弗里茨王有 bibi 个士兵，cici 个子民。
题目保证：
- ai+bi≡1(mod2)ai+bi≡1(mod2)
- ∑i=1nci≡1(mod2)i=1∑nci≡1(mod2)
请你计算你需要蛊惑最少的士兵数量。
输入格式
第一行一个正整数 nn，表示部落的数量。
接下来 nn 行，其中第 ii 行有三个整数 ai,bi,ciai,bi,ci。
输出格式
一个整数，表示需要蛊惑的最少士兵数量。
样例
Input 1
1 3 8 1
Output 1
3
Input 2
2 3 6 2 1 8 5
Output 2
4
Input 3
3 3 4 2 1 2 3 7 2 6
Output 3
0
Input 4
10 1878 2089 16 1982 1769 13 2148 1601 14 2189 2362 15 2268 2279 16 2394 2841 18 2926 2971 20 3091 2146 20 3878 4685 38 4504 4617 29
Output 4
86
样例解释
样例一中，只存在一个部落，蛊惑 33 个士兵之后，庆帝与弗里茨王的士兵数量分别为 6,56,5，该部落满足了庆帝的士兵数量大于弗里茨王的士兵数量，最后庆帝与弗里茨王的子民数量分别为 1,01,0，满足了庆帝的子民总数大于弗里茨王的子民总数。
样例二中，考虑第 22 个部落，蛊惑 44 个士兵之后，庆帝与弗里茨王的士兵数量分别为 5,45,4，该部落满足了庆帝的士兵数量大于弗里茨王的士兵数量.最后庆帝占领了第 22 个部落，弗里茨王占领了第 11 个部落，庆帝与弗里茨王的子民数量分别为 5,25,2，满足了庆帝的子民总数大于弗里茨王的子民总数。
数据范围
- 对于数据 1∼41∼4：1≤n≤101≤n≤10
- 对于数据 5∼105∼10：1≤n≤1001≤n≤100
- 对于所有数据：
- 1≤n≤1001≤n≤100
- 0≤ai,bi≤109,ai+bi≡1(mod2)0≤ai,bi≤109,ai+bi≡1(mod2)
- 1≤ci≤∑i=1nci≤105, ∑i=1nci≡1(mod2)1≤ci≤i=1∑nci≤105,i=1∑nci≡1(mod2)
#include<vector>
#include<cstdio>
#include<cstring>
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cuchar>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
using namespace std;
#define int long long
const int N = 114514 / 100;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int M = 114514 / 1000;
int dp[N];
int a[M], b[M], c[M];
signed main()
{
int n, sum = 0;
cin >> n;
for (int i = 1;i <= n;i++)
{
cin >> a[i] >> b[i] >> c[i];
sum += c[i];
}
memset(dp, INF, sizeof(dp));
dp[0] = 0;
for (int i = 1;i <= n;i++)
{
for (int j = sum;j >= c[i];j--)
{
dp[j] = min(dp[j], dp[j - c[i]] + max(0ll, (a[i] + b[i] + 1) / 2 - a[i]));
}
}
int ans = INF;
for (int i = sum / 2 + 1;i <= sum;i++)
{
ans = min(ans, dp[i]);
}
cout << ans << endl;
return 0;
}