记录编号	589422	评测结果	AAAWWWWWWW
题目名称	任务	最终得分	30
用户昵称	darkMoon	是否通过	未通过
代码语言	C++	运行时间	0.788 s
提交时间	2024-07-05 14:54:18	内存使用	143.57 MiB

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
//#define fin cin
//#define fout cout
ifstream fin("task.in");
ofstream fout("task.out");
auto mread = [](){
    int x;
    fin >> x;
    return x;
};
const int N = 3005;
int n = mread(), f[N][N][2], a[N], b[N];
signed main(){
    for(int i = 1; i <= n; i ++){
        a[i] = mread();
        b[i] = mread();
    }
    memset(f, 0x3f, sizeof(f));
    f[0][0][0] = f[0][0][1] = 0;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j <= a[i]; j ++){
            if(f[i][j][0] >= 1e18)
            continue;
            //tmp1 表示下一个转移的值，tmp2 表示下一个状态的第二维 
            //当前是 A 多，并且把第 i + 1 个物品放在 A 
            int tmp1 = f[i][j][0] + a[i + 1];
            int tmp2 = j + a[i + 1];
            tmp2 = min(tmp2, a[i + 1]);
            f[i + 1][tmp2][0] = min(f[i + 1][tmp2][0], tmp1);
            //当前是 A 多，并且把第 i + 1 个物品放在 B，此时 tmp1 不一定是转移的值， 
            //因为需要比较当前的 A 和 tmp1 的大小 
            tmp1 = f[i][j][0] - j + b[i + 1];
            if(f[i][j][0] >= tmp1){
                tmp2 = min(f[i][j][0] - tmp1, a[i + 1]);
                f[i + 1][tmp2][0] = min(f[i + 1][tmp2][0], f[i][j][0]);
            }
            if(f[i][j][0] <= tmp1){
                tmp2 = min(tmp1 - f[i][j][0], b[i + 1]);
                f[i + 1][tmp2][1] = min(f[i + 1][tmp2][1], tmp1);
            }
        }
        
        for(int j = 0; j <= b[i]; j ++){
            if(f[i][j][1] >= 1e18)
            continue;
            //tmp1 表示下一个转移的值，tmp2 表示下一个状态的第二维 
            //当前是 B 多，并且把第 i + 1 个物品放在 B 
            int tmp1 = f[i][j][1] + b[i + 1];
            int tmp2 = j + b[i + 1];
            tmp2 = min(tmp2, b[i + 1]);
            f[i + 1][tmp2][1] = min(f[i + 1][tmp2][1], tmp1); 
            //当前是 B 多，并且把第 i + 1 个物品放在 A，此时 tmp1 不一定是转移的值， 
            //因为需要比较当前的 B 和 tmp1 的大小 
            tmp1 = f[i][j][1] - j + a[i + 1];
            if(f[i][j][1] >= tmp1){
                tmp2 = min(f[i][j][1] - tmp1, b[i + 1]);
                f[i + 1][tmp2][1] = min(f[i + 1][tmp2][1], f[i][j][1]);
            }
            if(f[i][j][1] <= tmp1){
                tmp2 = min(tmp1 - f[i][j][1], a[i + 1]);
                f[i + 1][tmp2][0] = min(f[i + 1][tmp2][0], tmp1);
            }
        }
    }
    int ans = LONG_LONG_MAX;
    for(int i = 0; i <= 3000; i ++)
    ans = min({ans, f[n][i][0], f[n][i][1]});
    fout << ans;
}