题目链接：https://www.luogu.org/problemnew/show/P1282
花了好长时间终于写出了这道题，主要是状态转移方程比较奇葩，类似于背包问题，难以想到。
呃呃，写得DP不多，对于如何想出状态转移方程还没什么心得，主要是往之前见过的模型上靠。这道题的话，其实可以稍微转化一下设问，变成有n个数，每次操作可以将其变为相反数，问最少操作几次可以使总和的绝对值最小。设dp[i][j]为考虑到第i个数，总和为j时最少的操作次数。状态转移方程为dp[i][j]=min(dp[i-1][j-num[i]],dp[i-1][j+num[i]]+1)。因为是取最小值，一开始要把dp数组初始化成inf，还要将dp[0][0]初始化成0。反正代码细节也还是有的。
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=1e3+5,maxm=1e4+5,inf=0x3f3f3f3f; 4 int n,num[maxn],dp[maxn][maxm],mm[maxn],ans; 5 inline int abs(int x) {return x>0?x:-x;} 6 inline int map(int x) {return x+5e3+1;} 7 inline int min(int a,int b) {return a<b?a:b;} 8 int main() { 9 scanf("%d",&n); 10 int a,b,sum=0; 11 for(int i=1;i<=n;++i) {scanf("%d%d",&a,&b);num[i]=a-b;} 12 memset(dp,inf,sizeof(dp)); 13 for(int i=0;i<=n;++i) {dp[i][map(sum)]=0;sum+=num[i];mm[i]=mm[i-1]+abs(num[i]);} 14 for(int i=1;i<=n;++i) 15 for(int j=-mm[i];j<=mm[i];++j) 16 dp[i][map(j)]=min(dp[i-1][map(j-num[i])],dp[i-1][map(j+num[i])]+1); 17 for(int i=0;i<=mm[n];++i) 18 if(dp[n][map(i)]!=inf||dp[n][map(-i)]!=inf) { 19 ans=min(dp[n][map(i)],dp[n][map(-i)]); 20 break; 21 } 22 printf("%d",ans); 23 return 0; 24 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9609389.html
