【题目描述】
输入两个自然数，输出他们的和
【输入数据】
两个自然数x和y(0<=x,y<=32767)
【输出数据】
一个数，即x和y的和
【思路】
此题考查动态规划思想
首先我们需要把输入字符转换为数字a,b 然后使用动态规划求解A+B的值 最后输出答案
我们可以设计出如下DP方程
令f[j]表示i+j的值 则有
f[0][0]=0
f[j]=max{ f[i-1][j]+1, f[i][j-1]+1 }
由于对于每个i,j我们都要计算出f[j],因此时间复杂度与空间复杂度都为O(n^2)
但是 对于题目提供的最大数字n=32767明显超时！
【优化1】
对于DP方程 由于每次计算只需要f[i-1][j]或f[j-1]
因此我们可以使用滚动数组优化DP的空间复杂度
使用两个整数x,y分别保存f[i-1][j]与f[j-1]
空间复杂度降为O(2) 然而时间复杂度O(n^2)仍然超时!
“时间复杂度，到目前为止还没有更好的优化方法。因此，此题被称为史上最难的dp题!”
【优化2】
对于整数的运算 我们可以利用位运算的思想简化复杂度
题目显然要我们求两非负整数之和。
我们知道，在非负整数加法的二进制逻辑运算中，每一位上的结果取决于以下两方面：
1、本位上两个逻辑位的异或值
2、后一位的结果是否溢出
利用这种性质，可以考虑如下做法：
令f[j]表示，考虑两个加数的后i、j位相加的结果，显然有以下状态转移方程
f[j]= max { f[i][j-1]+y & (1 << (j-1)) f[i-1][j]+x & (1 << (i-1)) }
复制代码
赋初值f[0][0]=(x & 1) ^ (y & 1)
两个循环变量i,j从1循环到log(2,maxint)
我们成功的把时空复杂度降为O(log^2n)
利用滚动数组，可以进一步吧空间复杂度降为O(2)
至此,我们得到了一个较为圆满的解答
【题目评价】
此题实质上非常复杂
全面考察到了数学史和计算机史 经典代数 常用计算与输入输出 动态规划思想以及位运算思想等等等等知识点考虑到题目的所有可能性 我们应当从计算机存储的二进制的角度来逐步考虑数的表示 以字节计数，采用多字节合用的方式表示一个大整数如今已经是高级程序语言编译器轻松可以达到的目标可是为了加强对计算机计数的了解 此题可以考虑仍以最原始的方式进行计算——并且考虑最终将二进制数转变为十进制输出的全部过程 期间还考察了对ASCII码的熟悉程度。
而此题再RQNOJ上的通过人数竟然高达50% 可以看出RQNOJ上大牛之多 不禁令人感叹啊
【最小网络流题解】
program problem;
var
en,et,ec,eu,ep,ex:Array[0..250000] of longint;
dis:array[0..1000] of longint;
v:array[0..1000] of boolean;
i,j,k,n,m,w,cost,l:longint;
a,b,ans,left,right:longint;
function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b
end;
procedure addedge(s,t,c,u,k:longint);
begin
inc(l);
en[l]:=en[s];
en[s]:=l;
et[l]:=t;
ec[l]:=c;
eu[l]:=u;
ep[l]:=l+k;
end;
procedure build(s,t,u,c:longint);
begin
addedge(s,t,c,u,1);
addedge(t,s,-c,0,-1);
end;
function aug(no,m:longint):longint;
var
i,d:longint;
begin
if no=n then
begin
inc(cost,m*dis[1]);
exit;
end;
v[no]:=true;
i:=ex[no];
while i<>0 do
begin
if (eu[i]>0)and not v[et[i]] and(dis[et[i]]+ec[i]=dis[no]) then
begin
d:=aug(et[i],min(m,eu[i]));
if d>0 then
begin
dec(eu[i],d);
inc(eu[ep[i]],d);
ex[no]:=i;
exit(d);
end;
end;
i:=en[i];
end;
ex[no]:=i;
exit(0);
end;
function modlabel:boolean;
var
d,i,j:longint;
begin
d:=maxlongint;
for i:=1 to n do
if v[i] then
begin
j:=en[i];
while j<>0 do
begin
if (eu[j]>0)and not v[et[j]] and(ec[j]-dis[i]+dis[et[j]]<d) then
d:=ec[j]-dis[i]+dis[et[j]];
j:=en[j]
end;
end;
if d=maxlongint then exit(true);
for i:=1 to n do
if v[i] then
begin
v[i]:=false;
inc(dis[i],d);
end;
exit(false);
end;
function work:longint;
var i:longint;
begin
cost:=0;
repeat
for i:=1 to n do ex[i]:=en[i];
while aug(1,maxlongint)>0 do
fillchar(v,sizeof(v),0);
until modlabel;
work:=cost;
end;
function solve(x,d:longint):longint;
var i,k,t,p,last,cost,lk:longint;
begin
fillchar(en,sizeof(en),0);
fillchar(dis,sizeof(dis),0);
k:=0; n:=2; t:=x; p:=0;
while x<>0 do
begin
k:=k+x mod 10;
x:=x div 10;
inc(p);
end;
n:=1; x:=t; l:=k+p+1; last:=1; cost:=1; lk:=0;
while x<>0 do
begin
k:=x mod 10;
for i:=1 to k do
begin
inc(n);
build(last,n,1,-cost);
build(n,last+k+1,1,0);
end;
cost:=cost*10;
inc(n);
if last<>1 then
begin
if lk<k then
build(1,last,k-lk,0);
if k<lk then
build(last,n,lk-k,0);
end;
last:=n; x:=x div 10;
if lk<k then lk:=k;
end;
build(1,n,1,d);
solve:=-work;
end;
begin
readln(a,b);
left:=1; right:=1000000000;
while right-left>15000 do
begin
ans:=(left+right)shr 1;
if solve(ans,b)>a then
right:=ans
else left:=ans;
end;
for i:=left to right do
if solve(i,b)=a then
begin
writeln(i);
halt;
end;
end.
还有一位用什么一个PASCAL的面向对象的解法
program p1000;
var a,b,c:qword;
function max(a,b:qword):qword;
begin
if a<b
then exit(b)
else exit(a);
end;
function max(a,b:qword):qword;
begin
if a>b
then exit(b)
else exit(a);
end;
operator :=(a:qword):b:qword;
begin
b:=0;
if max(a,b)=a
then b:=max(a,b)
else b:=min(a,b);
end;
operator +(a,b:qword)c:qword;
begin
c:=0;
c:=max(a,b)+min(a,b);
end;
begin
readln(a,b);
c:=a+b;
writeln(c);
end.