题目链接：Poj1717 ， 洛谷1282 .
—————————————-
概述
给你
n
对数，每一对数分为上下两部分，这两个部分各有一个值，你可以交换上下两个数的位置。记上部分的和为s1，下部分的和为
s2
，现求使得
|s1−s2|
达到最小的交换次数。
—————————————-
题解
由题目的叙述我们可以知道，每一对数要么不交换，要交换最多被交换一次，因为再交换一次就会换回来。
咦？每一组数要么不操作，要么只操作一次，和01背包怎么那么像？
那我们试着用01背包的套路来定义状态，看看可不可行。
设
dp[i]
表示使
s1−s2=i
的最小操作数，初始化
dp[s1−s2]=0
，其它为
∞
。为了方便理解，
i
可以取到负数。
设ai表示初始时第
i
组数的上半部分，bi表示下半部分，那么此时这一组数
i
的差为d=ai−bi。 不妨先令
ai>bi
，假如我们选择不交换，那么差还是
d
，假如交换就变成了−d，
s1−s2
减少了
2×d
。
所以我们可以得到状态转移方程：
dp[i]=dp[i+2×d]+1.
对于
ai<bi
，交换之后会使
s1−s2
增加
2×d
，那么转移方程则是：
dp[i]=dp[i−2×d]+1.
最后统计答案的时候就从
dp[0]
开始左右扩展，假如有
dp[i]
不为
∞
，那么答案就是
dp[i].
差不多就是这样了？好像的确没有后效性。
至于
i
的下标会取到负数，我们可以将数组整体向数轴正半轴平移，这样就能使所有的i取到正数了。
—————————————-
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
#define For(i,j,k) for(register int i=j; i<=(int)k; ++i)
#define Forr(i,j,k) for(register int i=j; i>=(int)k; --i)
#define INF 0x3f3f3f3f
using namespace std;
const int maxn =
1000+
5;
const int num =
5050;
int n, s, Ans;
int a[maxn], dp[(maxn*
6)<<
1];
inline void read(
int &x){
char c;
while((c=getchar())<
'0' || c>
'9');
x = c^
48;
while((c=getchar())>=
'0' && c<=
'9')
x = x*
10+(c^
48);
}
inline void chkmin(
int &x,
int y){
if(y < x)
x = y;
}
int main(){
int x, y, d;
read(n);
For(i,
1, n){
read(x), read(y);
s += (a[i] = x-y);
}
memset(dp, INF,
sizeof(dp));
dp[s+num] =
0;
For(i,
1, n)
if(!a[i])
continue;
else if(a[i] >
0){
d = a[i]<<
1;
For(j, -
5000+num,
5000-d+num)
chkmin(dp[j], dp[j+d]+
1);
}
else{
d = (-a[i])<<
1;
Forr(j,
5000+num, -
5000+d+num)
chkmin(dp[j], dp[j-d]+
1);
}
Ans = INF;
if(dp[num] != INF) Ans = dp[num];
else{
For(i,
1,
5000){
if(dp[num-i] != INF) chkmin(Ans, dp[num-i]);
if(dp[num+i] != INF) chkmin(Ans, dp[num+i]);
if(Ans != INF)
break;
}
}
printf(
"%d", Ans);
return 0;
}
—————————————-
小结
此题考察的算法其实比较基础，重点在于分析问题原本的性质，即每一组数只有（不交换\交换一次）这两种选择。当分析出这题的本质就是01背包时，解法自然而然就出来了。
—————————————-
——wrote by miraclejzd.
