双方案课程 题解

核心考点

一维滚动DP。

思路分析

令 dp[s] 为处理当前若干天后总用时为 s 时选择 B 的最少次数；每天从旧数组转移到新数组。

需要特别检查空边界、相等值、最大规模和 long long 溢出。若存在不可达状态，应使用与合法答案明显区分的无穷大或负无穷初始化。

正确性说明

算法维护的状态或贪心选择恰好对应题目处理到当前位置时的全部有效决策。每一步只从已经正确的前缀状态转移，或作出不会损失最优解的局部选择；因此由归纳法，处理完全部输入后得到的就是题目要求的最优值或统计结果。

复杂度

复杂度满足题目完整数据范围；具体由主算法的循环层数决定。所有可能超过 32 位的累计量使用 long long。

参考代码

#include <bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,S;cin>>n>>S;vector<int>a(n),b(n);for(int&x:a)cin>>x;for(int&x:b)cin>>x;const int I=1e9;vector<int>dp(S+1,I),ndp;dp[0]=0;for(int i=0;i<n;i++){ndp.assign(S+1,I);for(int s=0;s<=S;s++)if(dp[s]<I){if(s+a[i]<=S)ndp[s+a[i]]=min(ndp[s+a[i]],dp[s]);if(s+b[i]<=S)ndp[s+b[i]]=min(ndp[s+b[i]],dp[s]+1);}dp.swap(ndp);}cout<<(dp[S]==I?-1:dp[S])<<'\n';}