Jennie

从左往右处理骨牌，需要知道什么就可以确定状态了？

需要知道当前的差值，然后dp决定取不取反

怎样知道差值

当然是扔到状态里

然后这就是一个背包了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int f[3][18000];
int key=7000;
int a[10001];
int cha;
int maxx=0;
int x,y;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&x,&y);
        a[i]=x-y;
        cha+=max(x-y,y-x);
    }
    memset(f,0x3f,sizeof(f));
    f[0][key]=0;
    maxx=f[0][1];
    for(int i=1;i<=n;++i){
        int p=(i+1)&1;
        int no=i&1;
        if(i==n)
        no=2;
        memset(f[no],0x3f,sizeof(f[no]));
        for(int j=key-cha;j<=key+cha;++j){
    //      if(j-a[i]>=key-cha&&j-a[i]<=key+cha);
            f[no][j]=min(f[p][j-a[i]],f[no][j]);
    //      if(j+a[i]>=key-cha&&j+a[i]<=key+cha);
            f[no][j]=min(f[p][j+a[i]]+1,f[no][j]);
        } 
    }
    for(int i=0;i<=cha;++i){
        int no=2;
        if(f[no][key+i]!=maxx){
            printf("%d",f[no][key+i]);
            return 0;
        }
        if(f[no][key-i]!=maxx){
            printf("%d",f[no][key-i]);
            return 0;
        }
    }
    return 0;
}