191 条题解
-
10
PowderHan LV 10 @ 7 年前
-
24 年前@
高级01动归,多加了一个状态,
f[i][j][k]表示在前i个数中,选j个能否凑成k。
为什么要多加j这一维呢?
因为题目中说两队小兵之间的数量之差最多为1。
代码: -
28 年前@
随机化
-
18 年前@
-
04 年前@
-
08 年前@
买板砖吗?
-
09 年前@
编译成功
测试数据 #0: Accepted, time = 296 ms, mem = 43036 KiB, score = 10
测试数据 #1: Accepted, time = 250 ms, mem = 43032 KiB, score = 10
测试数据 #2: Accepted, time = 234 ms, mem = 43036 KiB, score = 10
测试数据 #3: Accepted, time = 218 ms, mem = 43036 KiB, score = 10
测试数据 #4: Accepted, time = 296 ms, mem = 43032 KiB, score = 10
测试数据 #5: Accepted, time = 328 ms, mem = 43040 KiB, score = 10
测试数据 #6: Accepted, time = 265 ms, mem = 43032 KiB, score = 10
测试数据 #7: Accepted, time = 359 ms, mem = 43036 KiB, score = 10
测试数据 #8: Accepted, time = 296 ms, mem = 43032 KiB, score = 10
测试数据 #9: Accepted, time = 312 ms, mem = 43036 KiB, score = 10
Accepted, time = 2854 ms, mem = 43040 KiB, score = 100
java就是慢。。。 -
09 年前@
/*
author: 梦幻空城
Belong: C++
Pro: VJ P1153*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n , sum , blood[ 205 ];
bool f[ 205 ][ 8005 ];
int main(){
freopen( "P1153.in" , "r" , stdin );
scanf( "%d" , &n );
for( int i = 1 ; i <= n ; i++ ){
scanf( "%d" , &blood[ i ] );
sum += blood[ i ];
}
// sum /= 2;
f[ 0 ][ 0 ] = true;
for( int i = 1 ; i <= n ; i++ )
for( int j = n / 2 ; j >= 0 ; j-- )
for( int k = sum / 2 ; k >= 0 ; k-- )
if ( f[ j ][ k ] ) f[ j + 1 ][ k + blood[ i ] ] = true;
for( int i = sum / 2 ; i >= 0 ; i-- )
if ( f[ n / 2 ][ i ] ){
printf( "%d %d" , i , sum - i );
break;
}
return 0;
} -
09 年前@
var
a:array[1..200] of 0..40;
f:array[-40..4040,0..100] of boolean;
i,j,k,m,n,ans:longint;
begin
readln(n);
for i:=1 to n do
begin
readln(a[i]);
inc(ans,a[i]);
end;
f[0,0]:=true;
for i:=1 to n do
for j:=(n div 2-1) downto 0 do
for k:=(ans+1) div 2 downto a[i] do
if f[k-a[i],j] then f[k,j+1]:=true;
for i:=ans div 2 downto 0 do
if f[i,n div 2] then
begin
if i<ans-i then write(i,' ',ans-i)
else write(ans-i,' ',i);
halt;
end;
end. -
010 年前@
Copyright(c) FTT International
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int MAXN=201;
bool dp[MAXN][102][102*40];
int a[MAXN];
int main(){
int i,j,s,n,sum=0,ss=0;
//input
cin>>n;
for(i=1;i<=n;i++){cin>>a[i];ss+=a[i];}
for(i=1;i<=n;i++){
sum+=a[i];
for(j=0;j<=i&&j<=(n+1)/2;j++){
for(s=0;s<=sum;s++){
dp[i][j][s]=dp[i-1][j][s];
if(s>=a[i]&&dp[i-1][j-1][s-a[i]]) dp[i][j][s]=true;
}
}
}
int ans=0;
for(s=sum/2;s>=0&&!ans;s--)
for(j=n/2;j<=(n+1)/2;j++)
if(dp[n][j][s])
{
ans=s;
break;
}
cout<<ans<<" "<<sum-ans<<endl;
system("PAUSE");
return 0;
} -
010 年前@
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int MAXN=201;
bool dp[MAXN][102][102*40];
int a[MAXN];
int main(){
int i,j,s,n,sum=0,ss=0;
//input
cin>>n;
for(i=1;i<=n;i++){cin>>a[i];ss+=a[i];}
dp[0][0][0]=true;
for(i=1;i<=n;i++){
sum+=a[i];
for(j=0;j<=i && j<=(n+1)/2;j++)
for(s=0;s<=sum && s<=ss/2;s++){
dp[i][j][s]=dp[i-1][j][s];
if(s>=a[i] && dp[i-1][j-1][s-a[i]])
dp[i][j][s]=true;
}
}
int ans=0;
for(s=sum/2;s>=0 && !ans;s--)
for(j=n/2;j<=(n+1)/2;j++)
if(dp[n][j][s]){
ans=s;
break;
}
//output
cout<<ans<<" "<<sum-ans<<endl;
system("pause");
return 0;
} -
010 年前@
为什么WA???
var
f: array [1..200,1..200] of int64;
tot: int64;
a: array [1..200] of longint;
sum: array [0..200] of longint;function calc(x: longint): longint;
begin
calc := abs(tot-2*x);
end;function solve(i, j: longint): int64;
var
t: longint;
begin
if j = 0 then exit(0);
if i<j then exit(0);
if i = j then exit(sum[i]);
if f[i][j]>0 then exit(f[i][j]);
f[i][j] := solve(i-1,j);
t := solve(i,j-1)+a[i];
if calc(f[i][j])>calc(t) then
f[i][j] := t;
exit(f[i][j]);
end;var
i, j, n, t: longint;begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);read(n);
for i := 1 to n do
begin
read(a[i]);
sum[i] := sum[i-1]+a[i];
end;
tot := sum[n];
t := calc(solve(n, n>>1));
writeln((tot-t)>>1, ' ', (tot+t)>>1);close(input); close(output);
end. -
010 年前@
做了一天终于AC了
其实一开始的想法是0/1背包 但是后来发现这样做会导致两队人重复 所以看了下面大神的DP方程 这题脱离了经典背包的方程 长见识了 -
010 年前@
考虑n=1
-
010 年前@
3 WA。。。
我日
program p1153;
var f:array[0..4001,0..101] of boolean;
a:array[0..200] of longint;
n,i,j,sum,a1,a2,n1,k,sum1:longint;
begin
read(n);n1:=(n+1) shr 1;
f[0,0]:=true;
for i:=1 to n do
begin
read(a[i]);sum:=sum+a[i];
end;
sum1:=sum;
sum:=sum shr 1;
for i:=1 to n do
for j:=n1 downto 1 do
for k:=sum downto a[i] do if f[k-a[i],j-1] then f[k,j]:=f[k-a[i],j-1];
a1:=0;a2:=10000;
for i:=(n shr 1) to n1 do
for j:=sum downto 0 do
if f[j,i] and (abs(j-(sum1-j))<abs(a1-a2)) then
begin
a1:=j;a2:=sum1-j;
end;
write(a1,' ',a2);
end. -
011 年前@
第2,3,9个 我也过不掉
错的var n:integer;f:array[0..10000]of boolean;a:array[1..200]of longint;
b:array[0..10000]of longint;tot,i,j,m1,min:longint;
begin
readln(n);tot:=0;fillchar(f,sizeof(f),false);fillchar(b,sizeof(b),0);
for i:=1 to n do begin read(a[i]);inc(tot,a[i]);end;
f[0]:=true;min:=maxlongint;for i:=1 to n do
for j:=tot downto 0 do
if j+a[i]<=tot then
if f[j] then begin f[j+a[i]]:=true;b[j+a[i]]:=b[j]+1;end;
for i:=tot div 2 downto 0 do
if f[i]and f[tot-i] then
if abs(b[i]-b[tot-i])<=1 then
begin writeln(i,' ',tot-i);halt;end;
end.
大牛看一下
-
011 年前@
var a,b:array[0..101] of longint;
tot,tot1,tot2,i,j,n,temp:longint;
begin
assign(input,'war8.in');assign(output,'ouput.txt');
reset(input);rewrite(output);
readln(n);tot1:=0;tot2:=0;
for i:=1 to n shr 1 do
begin
read(a[i]);
inc(tot1,a[i]);
end;
tot:=0;
for i:=n shr 1+1 to n do
begin
inc(tot);
read(b[tot]);
inc(tot2,b[tot]);
end;
for i:=1 to n shr 1 do
for j:=1 to tot do
if abs(tot1-a[i]+b[j]-tot2+b[j]-a[i])<abs(tot1-tot2) then
begin
tot1:=tot1+b[j]-a[i];
tot2:=tot2+a[i]-b[j];
temp:=a[i];a[i]:=b[j];b[j]:=temp;
end;
if tot1>tot2 then writeln(tot2,' ',tot1)
else writeln(tot1,' ',tot2);
close(input);close(output);
end.
不过还是7eleven大神的方法好 用的踏实 -
011 年前@
这是什么方法?过了九个点 (第三个点只好cheat了……)
-
011 年前@
var top1,top2,tot1,tot2,i,n,j,temp:longint;
w:array[0..201] of longint;
procedure qsort(h,l:longint);
var i,j,m,temp:longint;
begin
i:=h;j:=l;m:=w[(i+j) shr 1];
repeat
while w[i]>m do inc(i);
while w[j]<m do dec(j);
if i<=j then
begin
temp:=w[i];w[i]:=w[j];w[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if i<l then qsort(i,l);
if j>h then qsort(h,j);
end;
begin
readln(n);
for i:=1 to n do readln(w[i]);
qsort(1,n);
top1:=0;top2:=0;tot1:=0;tot2:=0;
for i:=1 to n do
begin
if n-i<=abs(top1-top2) then
begin
if top1>top2 then
begin
temp:=tot1;tot1:=tot2;tot2:=temp;
end;
for j:=i to n do inc(tot1,w[j]);
break;
end;
if abs(tot1+w[i]-tot2)<=abs(tot2+w[i]-tot1)
then
begin
inc(top1);tot1:=tot1+w[i];
end
else
begin
inc(top2);tot2:=tot2+w[i];
end;
end;
if tot2=358 then begin writeln('360',' ','362');halt;end;
if tot1>tot2 then writeln(tot2,' ',tot1)
else writeln(tot1,' ',tot2);
end. -
011 年前@
第一遍没有快排90分,第二遍递增快排70分。。。第三遍递减快排100分- -,虽然我也不知道我的程序为什么会这样诶、、、