G.小红的数轴移动（二）

Solution

首先看到这个题，大家的第一印象是如何克服第二次操作朝向原点方向移动距离这个操作。

让我们来思考一个问题，如果我们只考虑只执行第一次操作，我们可以把这个问题变化为背包问题。用背包问题找到总距离的最小值，并且用last[i][j]保存上一次的操作来得出操作的方案。（背包问题的经典操作）

现在我们有了操作的方案，我们怎么去考虑第二个问题？

我们可以采取构造的方式，我们的操作有两种，一个是加上一个数，一个是减去一个数。将操作分为两个集合。

如果当前在正半轴，我们就用减去一个数的集合里挑选一个操作并且减去这个数，如果在正半轴，同理。最后一定能够回到原点。

剩下的操作都是不操作的，那我们直接放到末尾即可。

在赛时，这个题貌似数据出锅了，出现了无解的情况23333。可能这才是通过率低的缘故吧。

代码实现：

const int N = 4050 ;
 
// const int N = 1e6 + 10 ;
typedef pair<int , int> pii ;
typedef pair<double , double> pdd ;
const int inf = 1e9 + 10 ;
const int M = 2 * N ; 
const int mod = 998244353 ;
const double pi = acos(-1) ; 
 
int delta = 2010 ;
int dp[N][N] ;
int last[N][N] ; 
int a[N] ;
 
void solve() {
    memset(dp , 0x3f , sizeof dp) ;
    int n = read() , x = read() ;
    dp[0][delta + x] = 0 ;
    for(int i = 1 ; i <= n ; i ++) a[i] = read() ;
    for(int i = 0 ; i < n ; i ++){
        for(int j = 0 ; j < N ; j ++){
            if(j + a[i + 1] < N){
                if(dp[i + 1][j + a[i + 1]] > dp[i][j] + a[i + 1]){
                    dp[i + 1][j + a[i + 1]] = dp[i][j] + a[i + 1] ;
                    last[i + 1][j + a[i + 1]] = 1 ;
                }
            }
            if(dp[i + 1][j] > dp[i][j]){
                dp[i + 1][j] = dp[i][j] ;
                last[i + 1][j] = 0 ;  
            }
            if(j - a[i + 1] >= 0){
                if(dp[i + 1][j - a[i + 1]] > dp[i][j] + a[i + 1]){
                    dp[i + 1][j - a[i + 1]] = dp[i][j] + a[i + 1] ;
                    last[i + 1][j - a[i + 1]] = -1 ;
                }
            }
        }
    }
    if(dp[n][delta] > 1e7){
        int ans = 0 ;
        for(int i = 1 ; i <= n ; i ++) ans += a[i] ;
        write(ans , '\n') ;
        for(int i = 1 ; i <= n ; i ++) write(i , ' ') ;
         
        return ; 
    }
 
    cout << dp[n][delta] << endl ;
    vector<int> xx,yy,zz;
    int ax = n , ay = delta ;
    while(ax){
        if(last[ax][ay] == 0) xx.push_back(ax) ;
        else if(last[ax][ay] > 0) yy.push_back(ax) ;
        else zz.push_back(ax) ;
        ay -= last[ax][ay] * a[ax] ;
        ax -- ; 
    }   
    ay = delta + x ;
    while(ay != delta){
        if(ay < delta){
            ay += a[yy.back()] ;
            write(yy.back() , ' ') ;
            yy.pop_back() ; 
        }else{
            ay -= a[zz.back()] ;
            write(zz.back() , ' ') ;
            zz.pop_back() ; 
        }
    }
    while(xx.size()){
        write(xx.back() , ' ') ;
        xx.pop_back() ;
    }
}