记录编号	589485	评测结果	AAAAAAAAAA
题目名称	任务	最终得分	100
用户昵称	flyfree	是否通过	通过
代码语言	C++	运行时间	2.452 s
提交时间	2024-07-06 09:27:55	内存使用	465.87 MiB

#include<bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define ll long long
ll a[MAXN][5],dp[MAXN][MAXN*3][5];
ll n,ans=LONG_LONG_MAX;
int main(){
    freopen("task.in","r",stdin);
    freopen("task.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i][0]>>a[i][1];
    }
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<=3000;i++){
        dp[1][i][0]=0;
        dp[1][i][1]=0;
    }
    for(int i=1;i<=n;i++){
        for(int p=0;p<=1;p++){
            for(int j=0;j<=3000;j++){
                if(dp[i][j][p]==-1)continue;
//                cout<<i<<" "<<p<<"   "<<j<<" "<<dp[i][j][p]<<endl;
                if(j<=a[i][p]){
                    if(dp[i+1][0][p]==-1||dp[i][j][p]+a[i][p]<dp[i+1][0][p]){
                        dp[i+1][0][p]=dp[i][j][p]+a[i][p];
                        if(i==n)ans=min(ans,dp[i+1][0][p]);
//                        cout<<i<<" "<<p<<"  "<<j<<" "<<dp[i][j][p]<<" "<<dp[i+1][0][p]<<endl;
                    }
                    if(dp[i+1][a[i][p]-j][!p]==-1||dp[i+1][a[i][p]-j][!p]>dp[i][j][p]+j){
                        dp[i+1][a[i][p]-j][!p]=dp[i][j][p]+j;
                        if(i==n)ans=min(ans,dp[i+1][a[i][p]-j][!p]+a[i][p]-j);
                    }
                }else{
                    if(dp[i+1][j-a[i][p]][p]==-1||dp[i+1][j-a[i][p]][p]>dp[i][j][p]+a[i][p]){
//                        cout<<"j-a[i][p]:"<<j-a[i][p]<<" "<<dp[i][j][p]+a[i][p]<<endl;
                        dp[i+1][j-a[i][p]][p]=dp[i][j][p]+a[i][p];
                        if(i==n)ans=min(ans,dp[i+1][j-a[i][p]][p]+j-a[i][p]);
                    }
                    if(dp[i+1][0][!p]==-1||dp[i+1][0][!p]>dp[i][j][p]+j){
                        dp[i+1][0][!p]=dp[i][j][p]+j;
                        if(i==n)ans=min(ans,dp[i+1][0][!p]);
//                        cout<<i<<" "<<p<<"  "<<j<<" "<<dp[i][j][p]<<" "<<dp[i+1][0][p]<<endl;   
                    }
                }
           } 
       }
    }
    cout<<ans;
    return 0;
}