cf935：D.Seraphim the Owl（贪心）
题目
大家排成 𝑛n 队，从 𝑖=1i=1 号开始，向猫头鹰谢拉菲姆请教生命的意义。不巧的是，基里尔正忙着为这个问题编写传说，所以他来得晚了一些，站在了 𝑛n 这个人之后，排在了队伍的最后。基里尔对这种情况完全不满意，于是他决定贿赂一些排在他前面的人。
对于队列中的 𝑖i /第三个人，基里尔知道两个值： 𝑎𝑖ai 和 𝑎𝑖ai ： 𝑎𝑖ai 和 𝑏𝑖bi 。如果此刻基里尔站在 𝑖i 位置，那么他可以选择 𝑗j 这样的任意位置 𝑗<𝑖j<i ，与 𝑗j 位置的人交换位置。在这种情况下，基里尔需要支付他 𝑎𝑗aj 个金币。而对于 𝑘k 中的每一个 𝑗<𝑘<𝑖j<k<i ，基里尔都要向位置 𝑘k 的人支付 𝑏𝑘bk 个硬币。基里尔可以任意多次执行此操作。
基里尔很节俭，所以他想花尽可能少的硬币，但是他又不想等太久，所以基里尔认为他应该排在 𝑚m 人的前面。
请帮助基里尔确定，为了不等太久，他最少需要花费多少硬币。
输入
每个测试由几组输入数据组成。第一行包含一个整数 𝑡t ( 1≤𝑡≤1041≤t≤104 ) - 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含两个整数 𝑛n 和 𝑚m ( 1≤𝑚≤𝑛≤2000001≤m≤n≤200000 ) --分别是除基里尔之外的队列人数和基里尔最终位置的最大允许值。
第二行包含 𝑛n 个整数 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an ，用空格分隔( 1≤𝑎𝑖≤1091≤ai≤109 )。
第三行包含 𝑛n 个整数 𝑏1,𝑏2,…,𝑏𝑛b1,b2,…,bn ，用空格隔开( 1≤𝑏𝑖≤1091≤bi≤109 )。
保证所有测试用例中 𝑛n 的值之和不超过 2⋅1052⋅105 。
输出
对于每个测试用例，输出一个整数 - Kirill 需要花费的最少金币数
做法
我们要走到前m个人以内，那么后面的人我们不管他怎么插队，反正每个人要么给他ai个金币，要么给他bi个金币，我们就选小的给就好了。然后到了前m个人的话，最终选择的位置必须给那个人ai个金币。
#include<bits/stdc++.h>
using namespace std;
int t,n,m;struct ty{long long a,b;
};long long qzh[200010];int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);vector<ty> v(n+1);for(int i=1;i<=n;i++){scanf("%lld",&v[i].a);}for(int i=1;i<=n;i++){scanf("%lld",&v[i].b);}for(int i=1;i<=n/2;i++){//倒序好处理一点swap(v[i],v[n+1-i]);}for(int i=1;i<=n;i++){qzh[i]=qzh[i-1]+min(v[i].a,v[i].b);}long long minn=0x3f3f3f3f3f3f3f3f;for(int i=n-m+1;i<=n;i++){minn=min(qzh[i-1]+v[i].a,minn);}cout<<minn<<endl;}
}最近在学dp嘛，感觉能用dp写，但复杂度降不下去，加上题目那的标记也说是动规，我还以为是哪里可以降低复杂度，没想到是贪心了。dp的话就要考虑是从哪个位置插队上来的最小，但其实根本就不用这么复杂。
#include<bits/stdc++.h>
using namespace std;
int t,n,m;
long long dp[200010];//考虑了前i个位置，最小金币为
struct ty{long long a,b;
};
long long qzh[200010];
int main(){scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);vector<ty> v(n+1);for(int i=1;i<=n;i++){scanf("%lld",&v[i].a);}for(int i=1;i<=n;i++){scanf("%lld",&v[i].b);}for(int i=1;i<=n/2;i++){swap(v[i],v[n+1-i]);}for(int i=1;i<=n;i++){qzh[i]=qzh[i-1]+v[i].b;}memset(dp,0x3f3f3f3f3f3f3f3f,sizeof(dp));dp[0]=0;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){dp[i]=min(dp[i],dp[j]+v[i].a+qzh[i-1]-qzh[j]);}}long long minn=0x3f3f3f3f3f3f3f3f;for(int i=n-m+1;i<=n;i++) minn=min(dp[i],minn);cout<<minn<<endl;}
}