交换邻项得到序列
这一类题目一般都是牵扯到顺序的, AB 和 BA 得到的价值是不一样的, 这个时候就会通过研究局部最优解来得到一个全局最优解, 如果原来是 AB, 在某种条件 Cond 下, BA 的价值更大, 那么就交换 AB 的顺序变成 BA, 我们也就可以使用条件 Cond 来对整个序列进行排序
125. 耍杂技的牛 - AcWing 题库
这道题目, 我们考虑第 i 头牛和第 i+1 头牛交换前和交换后的风险值
| 交换前 | 交换后 | |
| i | C-s[i] | C-s[i+1] |
| i+1 | C+w[i]-s[i+1] | C+w[i+1]-s[i] |
我们可以发现 C+wi−si+1 一定 大于 C−Si+1 , C+wi+1−si一定大于 C−si, 所以这四个数的最大值一定出自 C+wi−si+1 和 C+wi+1−si
当wi+1−si<wi−si+1时, 也就是 wi+1+si+1<wi+si, 综合以上分析, 交换才会是风险值的最大值变小, 重载 bool operator<() 返回 false 发生交换, 把每头牛按照 w+s 来从小到大排序得到的序列, 其风险值的最大值最小
#include<iostream> #include<algorithm> using namespace std; const int NN=50010; struct Cow{ int w,s; bool operator<(Cow& c){ return w+s<c.w+c.s; } }cow[NN]; int n; // 贪心策略 研究相邻两项的交换来确定整体排序 int main(){ cin>>n; for(int i=0;i<n;i++){ int w,s; scanf("%d%d", &w, &s); cow[i]={w, s}; } sort(cow, cow+n); int danger=-2e9; int w_s=0; for(int i=0;i<n;i++){ danger=max(danger, w_s-cow[i].s); w_s+=cow[i].w; } cout<<danger<<endl; return 0; }
734. 能量石 - AcWing 题库
在这道题目当中, 需要考虑的问题有:
- 选择哪些能量石
- 以什么样的顺序吃选到的能量石
我们可以先考虑所有能量石, 找到一个最合适的拓扑序列, 这样就把能量石的食用循序确定了下来( 这是交换相邻项得序列问题 ), 之后再从这个序列中选中最优一个子序列 ( 这是一个 01 背包问题 ), 进一步把吃那些能量石也确定了下来
| 获得的能量 | |
| 交换前 | E'[i]+E'[i+1]-S[i]*L[i+1] |
| 交换后 | E'[i]+E'[i+1]-S[i+1]*L[i] |
当满足 E'[i]+E'[i+1]-S[i+1]*L[i] > E'[i]+E'[i+1]-S[i]*L[i+1] 时, 也就是 S[i+1]*L[i] < S[i]*L[i+1] 时, 交换可以使得到的能量变大, bool operator<() 返回 false
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int NN=110, MM=10010; int T, N; struct Stone{ int s,e,l; bool operator<(Stone& rhs){ if(rhs.s*l<s*rhs.l) return false; return true; } }stone[NN]; int f[MM]; // f[j] 表示时间点恰好为 j 时, 获得能量的最大值, 因为这道题目需要精确的时间点来计算能量石的价值 int main(){ cin>>T; for(int idx=1;idx<=T;idx++){ memset(f, -0x3f, sizeof f); f[0]=0; cin>>N; for(int i=1;i<=N;i++){ int s, e, l; scanf("%d%d%d", &s, &e, &l); stone[i]={s,e,l}; } sort(stone+1, stone+1+N); for(int i=1;i<=N;i++){ for(int j=MM-1;j>=stone[i].s;j--){ int si=stone[i].s, ei=stone[i].e, li=stone[i].l; f[j]=max(f[j], f[j-si]+max(0, ei-(j-si)*li)); } } int res=0; for(int i=0;i<MM;i++){ res=max(res, f[i]); } printf("Case #%d: %d\n", idx, res); } }
关于背包问题的初始化问题
- 求方案数的初始化
- 体积至多 j，f[i] = 1, 0 <= i <= m，
- 体积恰好 j，f[0] = 1, 其余是 0
- 体积至少 j，f[0] = 1，其余是 0
- 求最值的初始化
- 体积至多j，f[i] = 0, 0 <= i <= m
- 体积恰好j，
- 当求价值的最小值：f[0] = 0, 其余是INF
- 当求价值的最大值：f[0] = 0, 其余是-INF
- 体积至少j，f[0] = 0，其余是INF
当体积至多为 j 的时候, 初始状态的所有 f[i] 都可以有 f[0] 转移过去, 所以 f[i]=f[0]
