本弱菜 rp爆了 用贪心A了这道题 结果好多大神问我什么时间空间咋这么少(因为贪心做的呗) 让我不胜屏营

那我就弱弱的发个自己的方法……仅供参考 无法证明其正确性…… 其实我连样例2都没过

(第一次 勿喷)

第一步

相同的抵消掉（这个不花费步数）

第二步

要从状态A转移到状态B 那么如果A中两个数加起来等于B中一个数那么就把他抵消掉（ans+1） 如果B中两个数加起

来等于A中一个数那么也抵消掉（ans+1）

第三步

如果第二步无法执行了 那么这么搞

A：a1 a2 a3 a4　　

B：b1 b2 b3

（我把A、B都维护成递增的）

假设 a4>b3 则把a4拆成b3 和 a4-b3

A：a1 a4-b3 a2 a3

B: b1 b2

(注意维护有序 反正长度最多为10嘛 要不了好长时间）

第四步

若A、B长度都为零 即全部抵消掉了 则退出输出答案

否则继续从第二步开始做起

样例一

1 2 3 4 5 6

7 7 7

->

2 3 4 5

7 7

->

3 4

7

->

空

空

ans=3

样例二 不好意思没过 我输出是7（所以劝你找个更靠谱的方法 我这个不保证正确性）

代码可能写起来会很麻烦 所以我用了滚动数组(仅仅为了写起来方便)来维护A、B

var o,x,i,j,k,ans,sum:longint;

a,b:array[0..1,0..10] of longint;

f1,f2:array[0..10] of boolean;

ok:boolean;

procedure refresh;

var i,y:longint;

begin

y:=1-x;//滚动数组

a[y,0]:=0;

for i:=1 to a[x,0] do

if (not f1[i]) then

begin

inc(a[y,0]);

a[y,a[y,0]]:=a[x,i];

end;

b[y,0]:=0;

for i:=1 to b[x,0] do

if (not f2[i]) then

begin

inc(b[y,0]);

b[y,b[y,0]]:=b[x,i];

end;

x:=y;//滚动数组

fillchar(f1,sizeof(f1),false);

fillchar(f2,sizeof(f2),false);

end;

begin

x:=0;//滚动数组初状态

read(a[x,0]); for i:=1 to a[x,0] do read(a[x,i]);

read(b[x,0]); for i:=1 to b[x,0] do read(b[x,i]);

for i:=1 to a[x,0]-1 do

for j:=i+1 to a[x,0] do

if a[x,i]>a[x,j] then

begin

o:=a[x,i]; a[x,i]:=a[x,j]; a[x,j]:=o;

end;

for i:=1 to b[x,0]-1 do

for j:=i+1 to b[x,0] do

if b[x,i]>b[x,j] then

begin

o:=b[x,i]; b[x,i]:=b[x,j]; b[x,j]:=o;

end;

//排下序

while true do

begin

for i:=1 to a[x,0] do

for j:=1 to b[x,0] do

if a[x,i]=b[x,j] then

begin

f1[i]:=true;

f2[j]:=true;

refresh;

end;

//相同的抵消

ok:=true;

while ok do

begin

ok:=false;

for i:=a[x,0]-1 downto 1 do

for j:=i+1 to a[x,0] do

for k:=b[x,0] downto 1 do

begin

if ok then break;

if a[x,i]+a[x,j]=b[x,k] then

begin

inc(ans);

f1[i]:=true;

f1[j]:=true;

f2[k]:=true;

refresh;

ok:=true;

end;

end;

end;

//A中两数和等于B中的话抵消

ok:=true;

while ok do

begin

ok:=false;

for i:=b[x,0]-1 downto 1 do

for j:=i+1 to b[x,0] do

for k:=a[x,0] downto 1 do

begin

if ok then break;

if b[x,i]+b[x,j]=a[x,k] then

begin

inc(ans);

f2[i]:=true;

f2[j]:=true;

f1[k]:=true;

refresh;

ok:=true;

end;

end;

end;

//B中两数和等于A中的话抵消

if a[x,a[x,0]]>b[x,b[x,0]] then

begin

inc(ans);

a[x,a[x,0]]:=a[x,a[x,0]]-b[x,b[x,0]];

dec(b[x,0]);

for i:=1 to a[x,0]-1 do

for j:=i+1 to a[x,0] do

if a[x,i]>a[x,j] then

begin

o:=a[x,i]; a[x,i]:=a[x,j]; a[x,j]:=o;

end;

end else

if a[x,a[x,0]]b[x,j] then

begin

o:=b[x,i]; b[x,i]:=b[x,j]; b[x,j]:=o;

end;

end;

//如果不能用前两种方法抵消就把最大的数拆分成 对面最大的+(最大的数-对面最大的)

inc(sum);

if sum>100000 then

begin

ans:=-1;

break;

//无解

end;

if (a[x,0]=0) and (b[x,0]=0) then break;//抵消完了就输答案

end;

writeln(ans);

end.

program p1758;
var
n,m:array[1..10] of byte;
usedn,usedm:array[1..10] of boolean;
fn,fm:array[0..5000,1..10] of byte;
sfn,sfm:array[0..5000] of boolean;
dn,dm:array[0..5000] of byte;
sumn,summ:integer;
numn,numm:byte;
min:integer;
x:byte;
ans:integer;
i,j,k:integer;
left:integer;
begin sumn:=0; summ:=0;ans:=0;
read(numn); for i:=1 to numn do begin read(n[i]); sumn:=sumn+n[i]; end;
read(numm); for i:=1 to numm do begin read(m[i]); summ:=summ+m[i]; end;
left:=numn+numm;
fillchar(usedn,sizeof(usedn),false);
fillchar(usedm,sizeof(usedm),false);
if summ<>sumn then writeln(-1)
else begin
while left>0 do begin
fillchar(sfn,sizeof(sfn),false);
fillchar(sfm,sizeof(sfm),false);
for i:=1 to sumn do begin dn[i]:=200; dm[i]:=200; end;
dn[0]:=0;
dm[0]:=0;
min:=500;
sfn[0]:=true;
sfm[0]:=true;
for i:=1 to numn do begin
for j:=sumn downto 0 do begin
if not(usedn[i]) and sfn[j] then
if dn[j]+1<dn[j+n[i]] then begin
for k:=1 to dn[j] do begin
fn[j+n[i],k]:=fn[j,k];end;
fn[j+n[i],dn[j]+1]:=i;
dn[j+n[i]]:=dn[j]+1;
sfn[j+n[i]]:=true;
end;
end;end;
for i:=1 to numm do begin
for j:=summ downto 0 do begin
if not(usedm[i]) and sfm[j] then
if dm[j]+1<dm[j+m[i]] then begin
for k:=1 to dm[j] do begin
fm[j+m[i],k]:=fm[j,k];end;
fm[j+m[i],dm[j]+1]:=i;
dm[j+m[i]]:=dm[j]+1;
sfm[j+m[i]]:=true;
end;
end;end;
for i:=sumn downto 1 do
if dn[i]+dm[i]<min then begin min:=dn[i]+dm[i]; x:=i;end;
ans:=ans+min-2;
for i:=1 to dn[x] do usedn[fn[x,i]]:=true;
for i:=1 to dm[x] do usedm[fm[x,i]]:=true;
left:=left-min;
end;
writeln(ans);
end;
end.
可以将N数组的分解看做M数组的合并
这道题贪心我已经可以局部证明但是不知道是否正确。。。
就是说最多次数是（N的元素个数+M的元素个数-2）
然后如果之前就可以合并，那么一定是被重复计入了的（例如 N:5 5 5 M: 10 3 2 最多4次 但是 5多了一次合并 3 2也多了一次合并 所以最小次数是5+5=10 3+2=5，即为2）

#include

#include

#include

#include

#include

#include

#include

using namespace std;

typedef long long ll;

typedef double db;

#define rep(i,n) for (int i = 0;i < n;++i)

#define repD(i,n) for (int i = n-1;i >= 0;--i)

#define For(i,a,b) for (int i = a;i = b;--i)

#define ForE(i,a) for (int i = a;i != -1;i = E[i].next)

#define sqr(a) ((a)*(a))

#define shl(a,b) ((a) > (b))

#define max(a,b) (a > b ? a : b)

#define min(a,b) (a < b ? a : b)

#define fill(a,b) memset(a,b,sizeof(a))

#define abs(x) ((x) > 0 ? (x) : (-(x)))

#define pb push_back

const int INF = 2147483647,maxN = 10+10,maxC = 1024+10,maxAll = 100000;

int N,M,tot = 0;

int A[maxN],B[maxN],sumA[maxC],sumB[maxC],nA[maxC],nB[maxC],qA[maxC],qB[maxC],sA[maxC],sB[maxC],cA[maxAll],cB[maxAll],s[maxAll],dp[maxC][maxC];

bool v[1000],used[maxC];

void setIO(string name)

{

string in = name + ".in";

string out = name + ".out";

freopen(in.c_str() , "r" , stdin);

freopen(out.c_str() , "w" , stdout);

}

int main()

{

//setIO("test");

int cnt = 0;

scanf("%d", &N);

rep(i,N) scanf("%d", &A[i]),cnt += A[i];

scanf("%d", &M);

rep(i,M) scanf("%d", &B[i]),cnt -= B[i];

if (cnt != 0) {

printf("-1\n");

return 0;

}

int r1 = 0;qA[0] = 0,sA[0] = 0,nA[0] = 0;

fill(v,0),fill(used,0);

rep(i,r1+1) rep(j,N) if ((shl(1,j) & qA[i]) == 0 && !used[shl(1,j) + qA[i]]) {

sA[++r1] = sA[i] + A[j];

qA[r1] = qA[i] + shl(1,j);

nA[r1] = nA[i] + 1;

v[sA[r1]] = used[qA[r1]] = true;

}

int r2 = 0;qB[0] = 0,sB[0] = 0,nB[0] = 0;

fill(used,0);

rep(i,r2+1) if (!v[sB[i]])

rep(j,M) if ((shl(1,j) & qB[i]) == 0 && !used[shl(1,j) + qB[i]]) {

sB[++r2] = sB[i] + B[j];

qB[r2] = qB[i] + shl(1,j);

nB[r2] = nB[i] + 1;

used[qB[r2]] = true;

}

For(i,1,r1) For(j,1,r2) if (sA[i] == sB[j]) {

cA[tot] = qA[i],cB[tot] = qB[j],s[tot++] = nA[i]+nB[j]-2;

}

For(i,1,shl(1,N)-1) {

sumA[i] = 0;

rep(j,N) if ((shl(1,j) & i) != 0) sumA[i] += A[j];

}

For(i,1,shl(1,M)-1) {

sumB[i] = 0;

rep(j,M) if ((shl(1,j) & i) != 0) sumB[i] += B[j];

}

For(i,1,shl(1,N)-1) For(j,1,shl(1,M)-1) dp[i][j] = 1000000;

For(i,1,shl(1,N)-1) For(j,1,shl(1,M)-1) if (sumA[i] == sumB[j])

rep(k,tot) if ((i & cA[k]) == cA[k] && (j & cB[k]) == cB[k])

dp[i][j] = min(dp[i][j],dp[i-cA[k]][j-cB[k]] + s[k]);

printf("%d\n", dp[shl(1,N)-1][shl(1,M)-1]);

return 0;

}

状态压缩DP

dp[M1][M2] (M1,M2

深搜里面嵌个背包..

背包一和背包二的都有消掉再搜，就过了..

#01: ---|---|---|---|---|---|---|---|-

Accepted (24ms, 580KB) 

#02: ---|---|---|---|---|---|---|---|-

Accepted (12ms, 580KB) 

#03: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

#04: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

#05: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

#06: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

#07: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

#08: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

#09: ---|---|---|---|---|---|---|---|-

Accepted (867ms, 580KB) 

#10: ---|---|---|---|---|---|---|---|-

Accepted (0ms, 580KB) 

第9个点…………………………差点跪了

前面那道逆序对题都因为各种小错ORZ的跪了N次，这题竟然1次AC了。什么玩意啊！！！

还有后面那道二次方程，虐爆人了有木有啊！！！

其实还是……贪心算法。

证明……不会……

大致思想和wcy童鞋是一样的。

相同的就消除掉。

能2个数进行合并的时候……

选择合起来最大的那个数进行合并！！

这样可以避免A和B能合成C，而C却还能和同行的其他数进行合并……

就如样例2的前行 1 4 20

后行 5 15

这样看来1和4并成5并不优秀，而5和15并起来更好。

如果不行，就选择a，b两行各最大的。把更大的那个分成小的那个和另外一个数即可。

OOOOOOOOOOOOORZ，这题到底是怎么1A的。。。

具体和wcy的想法差不多，顶多能把样例2给搞定了……