abc317D 选举总统

题面：有n个区，第i个区有x[i]+y[i]个选民，其中x[i]支持A，y[i]支持B，支持人数多的一方获得该区的全部票数z[i]，全部区的票数之和多者获胜，问至少还要多少选民从支持B改为支持A，才能让A胜出？
范围：1<=n<=100; 0<=x[i],y[i]<=1E9; x[i]+y[i]为奇数, z[i]>=1，z[i]之和为奇数且不超过1E5。

思路：将各个区看成物品，对于第i个区，如果x[i]>y[i]，那么花费为0；否则要让x[i]增加到过半数，花费为(x[i]+y[i]+1)/2 - x[i]。综合得，第i个区的花费为max(0, (y[i]-x[i]+1)/2)，价值为z[i]。
如果正常跑01背包，dp[i]表示花费为i时所能取到的最大价值，跑完后遍历dp找到值大于zsum/2的下标。但本题花费很大，而价值较小，因此定义dp[j]为取到价值j时所需的最小花费，跑完后遍历dp找到满足条件j值的最小dp[j]即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

const int N = 105;
const int M = 1E5+5;
const int inf = 1E18;
int n, m, c[N], w[N], dp[M];
void solve() {
    cin >> n;
    rep(i,1,n) {
        int x, y, z;
        cin >> x >> y >> z;
        c[i] = max(0LL, (y-x+1)/2);
        w[i] = z;
        m += z;
    }
    rep(i,1,m) dp[i] = inf;
    rep(i,1,n) per(j,w[i],m) {
        dp[j] = min(dp[j], dp[j-w[i]]+c[i]);
    }
    int ans = inf;
    rep(i,0,m) if(i+i>m) {
        ans = min(ans, dp[i]);
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}