Atcoder AWC 052 beta

2026-04-252026-04-25

vp 了一下

A 循环

找到最长连续递增序列

B 循环 取余

C 01背包

饺子醋这一块，其实就是为了这题来vp的，什么时候才能学会01背包啊！

\(n\)件商品，每件满意度\(V_i\)，价格\(C_i\)，每件商品最多只能购买一次，一共\(S\)元

是一道01背包模版题！

void solve() { 
  int n, s;
  cin >> n >> s;
  vector<int> v(n + 1), c(n + 1);
  for (int i = 1; i <= n; i ++) {
    cin >> v[i] >> c[i];
  }
  vector<int> dp(s + 1, INT_MIN / 2);
  dp[0] = 0;
  debug(dp);
  for (int i = 1; i <= n; i ++) { // 第i个商品
    int cur_v = v[i], cur_c = c[i];
    for (int j = s; j >= 0; j --) { // 能否转移到花费j元？
      if (j - cur_c >= 0) dp[j] = max(dp[j], dp[j - cur_c] + cur_v);
    }
  }
  cout << ((dp[s] > 0) ? dp[s] : -1) << endl;
}

D 二进制枚举/搜索/状压

后续补题

E 状压DP（TSP旅行商问题）

后续补题