这是第一个c++题解吗。。。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
const int maxn = 6001,inf = 0x7f7f7f7f;
int f[maxn],a[1010],b[1010];
int main () {
    int  k,m = 0,n,sum = 0;
    scanf ("%d",&n); 
    for (int i=1;i<=n;i++) {
        scanf ("%d%d",a+i,b+i);
        m += max(a[i],b[i]); 
        sum += a[i] + b[i]; 
    }
    memset (f,inf,sizeof f); 
    f[0] = 0; 
    for (int i=1;i<=n;i++) 
        for (int j=m;j>=0;j--) {
            int ans = inf; 
            if ( j >= a[i] )
                ans = f[j-a[i]];
            if ( j >= b[i] )
                ans = min(ans,f[j-b[i]]+1);
            f[j] = ans;
        }
    for (int i=sum>>1;i;i--) {
        k = min(f[i],f[sum-i]);
        if ( k < inf ) {
            printf("%d\n",k) ;
            return 0 ;
        }
    }
    return 0 ;
}

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
const int maxn = 6001,inf = 0x7f7f7f7f;
int f[maxn],a[1010],b[1010];
int main () {
int k,m = 0,n,sum = 0;
scanf ("%d",&n);
for (int i=1;i<=n;i++) {
scanf ("%d%d",a+i,b+i);
m += max(a[i],b[i]);
sum += a[i] + b[i];
}
memset (f,inf,sizeof f);
f[0] = 0;
for (int i=1;i<=n;i++)
for (int j=m;j>=0;j--) {
int ans = inf;
if ( j >= a[i] )
ans = f[j-a[i]];
if ( j >= b[i] )
ans = min(ans,f[j-b[i]]+1);
f[j] = ans;
}
for (int i=sum>>1;i;i--) {
k = min(f[i],f[sum-i]);
if ( k < inf ) {
printf("%d\n",k) ;
return 0 ;
}
}
return 0 ;
}

我的题解

法一：

本问题可归约为经典的背包问题。

假设一碗拉面的重量差的绝对值是s，那么它实际可以取到的重量差就是-s或s。我们不妨对取值进行一下平移，让每碗拉面可以取到的点数差为0和2s。这样，拉面的“取正值还是负值”就转化为背包的“取与不取”了。

那么，我们求解的目标会怎样变化呢？本来，我们的目标是让取值的总和为0。现在，我们对每碗拉面的取值作了平移，平移的距离为s。那么，最后的取值总和就应该是∑s，即所有拉面的平移距离之和。

方法二：

我们用数组a[ i]表示第i碗拉面的上下重量之差，用F表示用前i 碗拉面上下差值为j时所要的最少操作次数，那么有

f:=min(f[i-1,j-a[ i]],f[i-1,j+a[ i]]+1);

最后的答案为f[n,k],其中k是最接近0的可能得到的数值。

考虑到空间问题，数组可以采用滚动数组实现

f[i][j]表示前i个数，换j次的绝对值最小时对应的值，过了8个点
f[i][j]表示前i个数，得到差为j时的最小换的次数，ac
求教原因。。。

const t=2500;
var
f,ff:array[-t..t] of boolean;
s,ss:array[-t..t] of longint;
n,i,x,y,l:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a);
exit(b);
end;
function ok(k:longint):boolean;
begin
if (k>=-2500) and (k<=2500) then exit(true);
exit(false);
end;
begin
readln(n);
fillchar(f,sizeof(f),false);
fillchar(s,sizeof(s),\(7f);
readln(x,y);
f[x-y]:=true;s[x-y]:=0;
f[y-x]:=true;s[y-x]:=1;
for l:=2 to n do
begin
readln(x,y);
fillchar(ff,sizeof(ff),false);
fillchar(ss,sizeof(ss),\)7f);
for i:=-t to t do
if f[i] then
begin
if ok(i+x-y) then
begin
ff[i+x-y]:=true;
if ss[i+x-y]>s[i] then ss[i+x-y]:=s[i];

end;
if ok(i-x+y) then
begin
ff[i-x+y]:=true;
if ss[i-x+y]>s[i]+1 then ss[i-x+y]:=s[i]+1;
end;
end;
f:=ff;
s:=ss;
end;
for i:=0 to t do
begin
if f[i] and f[-i] then
begin
writeln(min(s[i],s[-i]));
halt;
end;
if f[i] then
begin
writeln(s[i]);
halt;
end;
if f[-i] then
begin
writeln(s[-i]);
halt;
end;
end;
end.
其实也可以只开s数组，我为了方便。
第一遍交的时候，我搞错了一个地方：
我没有用滚动数组，直接在f和s上递推，只对了两个点。
但其实，第三个是不能从第一个直接转移，必须经过第二个可能的两种变换得到。
秒过。

asdf

滚动数组 + 遍读入遍处理 就可以秒杀了~

题解

http://hi.baidu.com/%C4%BE%D7%D3%C8%D5%D4%C8/blog/item/349e693cdfe4710abaa167f9.html

事实证明：

开两个数组f1,f2:array[-2600..2600]就好！

因为下一个的状态 只由上一个推来，所以用两个数组滚动就行。

因为1

f表示前i碗，上部比下部重j的最小操作数。

f=min{f,f+1}

边读变做，a和b均为当前读入的值。使用滚动数组能有效降低空间复杂度， 不用也能过。

初始化：fillchar(f,sizeof(f),$7f div 10);f[0,0]=0;

总耗时(6K):130ms

糟糕，赋初值出问题...

将搜索范围限定在-5*i..5*i很有效！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 72ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 40ms

├ 测试数据 10：答案正确... 72ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：240ms

我们学校为了“方便学生”在吃饭的时候封校！这就是差距啊！

program p1222;

var f:array[0..1000,-5000..5000] of longint;

a:array[0..1000] of longint;

i,j,k,l,m,n,o,p,q,min:longint;

function max(x,y:longint):longint;

begin if x

10分钟、、、没秒杀、我是沙茶、、、

折寿

背包今天穿上了拉面的马甲

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案错误...　├ 标准行输出 352

　├ 错误行输出 543

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

怎么回事???????????????????????????

背包+滚动数组就可以秒杀了

装箱。。。

用了传说中的“不复制滚动数组” 0.0|||

纯粹的滚动式装箱。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

小菜小菜，一次Ac!

用户信息 User Info

超子

---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|--

Level Member

提交 200次

通过 66题

通过率 33%

program v1222;

var a:array[0..1001] of shortint;

f:array[0..1001,-6000..6000] of dword;

i,j,k,n,x,y,w:longint;

function min(p,q:longint):longint;

begin

if p