但不知道怎么改
by DDOSvoid @ 2018-02-26 19:05:19
@[DDOSvoid](/space/show?uid=34531) 支持,同求。
by mzq667 @ 2018-02-26 19:07:20
话说谁知到为什么这个代码只能得 73 分== 求助
f[i][j] 表示前 i 个数,换了 j 次,第一组和第二组的差值的绝对值最小(但存的不是绝对值)
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
#define INF 1000000000
using namespace std;
int n, a[maxn], b[maxn], s1[maxn], s2[maxn], f[maxn][maxn];
inline int abs(int x){return x > 0 ? x : -x;}
int main(){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
memset(f, 10, sizeof f); f[0][0] = 0;
for(int i = 1; i <= n; ++i){
f[i][0] = f[i - 1][0] + a[i] - b[i];
for(int j = 1; j <= i; ++j){
if(abs(f[i - 1][j] + a[i] - b[i]) <= abs(f[i - 1][j - 1] + b[i] - a[i]))
f[i][j] = f[i - 1][j] + a[i] - b[i];
else f[i][j] = f[i - 1][j - 1] + b[i] - a[i];
}
}
int Min = INF, ans = INF;
for(int i = 0; i <= n; ++i)
if(abs(f[n][i]) < Min)
Min = abs(f[n][i]), ans = i;
cout << ans;
return 0;
}
```
by DDOSvoid @ 2018-02-26 19:10:32
您可以跑个背包然后滚去一维啊qwq
by 皎月半洒花 @ 2018-07-20 18:07:49