Rt，$f_{i,j}$ 表示到第 $i$ 个翻转 $j$ 次的最优解

#include <stdio.h>
#include <string.h>
int i,j,ans,n,mid=1<<30;
inline int abs(int s){
	return s<0?-s:s;
}
inline void chg(int a,int& b){
	if(abs(a)<b)
		b=a;
	return;
}
int f[1005][1005];
int a[1005],b[1005];
int main(){
	memset(f,0x3f,sizeof f);
	scanf("%d",&n);
	for(i=1;i<=n;++i)
		scanf("%d %d",a+i,b+i);
	for(j=0;j<=n;++j)
		f[0][j]=0;
	for(i=1;i<=n;++i)
		f[i][0]=f[i-1][0]+a[i]-b[i];
	for(i=1;i<=n;++i){
		for(j=1;j<i;++j){
			chg(f[i-1][j-1]+b[i]-a[i],f[i][j]);
			chg(f[i-1][j]+a[i]-b[i],f[i][j]);
	//		printf("%d ",f[i][j]);
		}
	//	printf("\n");
	}
	for(j=0;j<=n;++j)
		if(abs(f[n][j])<mid){
			mid=abs(f[n][j]);
			ans=j;
	//		printf("%d\n",f[i][j]);
		}
	printf("%d",ans);
	return 0;
}