D. Yet Another Minimization Problem

传送门：CF

前言：过完年的这么几把，把把掉大分，从1850调到1700，真实酸爽。这场D的dp是一个很妙的点（至少我不会），看了 小t 的代码后，醍醐灌顶（小t如药也，善读可以医愚）。

正文：

首先看下数据范围，给了2秒的实现加上n为100，我初解的时候觉得是一个暴力枚举的题，所以压根就没往化简式子+dp上面想。所以掉大分。

通过化简式子，可以得到，最优的时候是

当然，很难得到最完美的情况，所以只要尽量接近就行。

然而我们该怎么找到这个最优的和呢？

我最初的想法是暴力，但是MLE了（我是傻逼）

正解是通过迭代，AC代码如下：

#include
using namespace std;
#define ll long long

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T; 
    cin>>T;
	while(T--)
	{
        int n;
        cin>>n;
        vectora(n),b(n);
        for(int i=0;i>a[i];
        for(int i=0;i>b[i];
        if(n==1){
            cout<<0<<'n';
            continue;
        }
        ll sum = accumulate(a.begin(),a.end(),0)+accumulate(b.begin(),b.end(),0);
        vectordp(sum+1);
        dp[0]=1;
        for(int i=0 ;i= 0;j--){
                if(dp[j]){
                    dp[j+a[i]]=1;
                    dp[j+b[i]]=1;
                    dp[j]=0;
                }
            }
        }
        
        ll kase = 1e18;
        ll sum1=0;
        for(int i=0;i<=sum;i++){
            if(dp[i]==0)continue;
            if(abs(sum-i*2)>T;
	while(T--)
	{
        int n;
        cin>>n;
        vectora(n),b(n);
        for(int i=0;i>a[i];
        for(int i=0;i>b[i];
        if(n==1){
            cout<<0<<'n';
            continue;
        }
        ll sum = accumulate(a.begin(),a.end(),0)+accumulate(b.begin(),b.end(),0);
        vectordp(sum+1);
        dp[0]=1;
        for(int i=0 ;i= 0;j--){
                if(dp[j]){
                    dp[j+a[i]]=1;
                    dp[j+b[i]]=1;
                    dp[j]=0;
                }
            }
        }
        
        ll kase = 1e18;
        ll sum1=0;
        for(int i=0;i<=sum;i++){
            if(dp[i]==0)continue;
            if(abs(sum-i*2) 

这里又学了一个STL，
 
可以用accumulate（）来直接求解一个数组的和。