| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
哎,还枉费我想了各种复杂的情况...贴代码出来,哪位好心的大大看看这在C++和G++下有什么不同吧In Reply To:!!!!!!!!!!!!!!!!真的g++就过了...汗啊,到底是什么地方不同?__int64的问题? Posted by:dynamic at 2005-11-15 08:02:24 #include <vector>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <utility>
#include <iostream>
#include <sstream>
typedef __int64 integer;
int n,m;
int left[50],right[50],flag[50];
char s[3000],ss[3000];
integer v[3000],maxv,sum,a[51][51];
void dfs(int cur,int d)
{
if (left[cur]>=0) dfs(left[cur],d+1);
if (right[cur]>=0) dfs(right[cur],d+1);
sum+=v[cur]*d;
}
integer dp(int s,int t)
{
int i;
integer p=0,temp;
if (a[s][t]>=0) return a[s][t];
if (s>t){
a[s][t]=0;
return 0;
}
for(i=s;i<=t;i++) p+=v[i];
a[s][t]=maxv*3000;
for(i=s;i<=t;i++){
temp=dp(s,i-1)+dp(i+1,t)+p;
if (temp<a[s][t]) a[s][t]=temp;
}
return a[s][t];
}
bool construct(int s,int t)
{
int i,j,k;
integer p=0,temp;
if (s>t) return 1;
for(i=s;i<=t;i++) p+=v[i];
j=0;
for(i=s;i<=t;i++){
temp=dp(s,i-1)+dp(i+1,t)+p;
if (temp==a[s][t]){
k=i;
j++;
}
}
if (j>=2) return 0;
return construct(s,k-1) && construct(k+1,t);
}
bool solve()
{
int i,start,l=strlen(s);
bool zero;
for(i=0;i<l;i++){
if (s[i]!='\t' && s[i]!=' ' && !isdigit(s[i])) return 0;
}
m=0;
start=0;
integer temp=0;
zero=0;
for(i=0;i<=l;i++){
if (isdigit(s[i])){
if (!start && s[i]=='0'){
if (s[i+1]=='0') return 0;
zero=1;
}
start=1;
temp=temp*10+s[i]-'0';
if (temp>maxv) return 0;
}else if (start){
v[m++]=temp;
if (zero==1 && temp!=0) return 0;
temp=0;
start=0;
zero=0;
}
}
if (m!=n) return 0;
sum=0;
memset(flag,0,sizeof(flag));
for(i=0;i<n;i++){
if (left[i]>=0) flag[left[i]]=1;
if (right[i]>=0) flag[right[i]]=1;
}
for(i=0;i<n;i++) if (!flag[i]) break;
dfs(i,1);
if (sum==0) return 0;
memset(a,0xff,sizeof(a));
if (sum!=dp(0,n-1)) return 0;
if (!construct(0,n-1)) return 0;
return 1;
}
int main()
{
// freopen("test.txt","r",stdin);
int i;
maxv=1;
for(i=0;i<15;i++) maxv*=10;
while(1){
gets(s);
if (strcmp(s,"#End#")==0) break;
if (strcmp(s,"#Start Input#")!=0) continue;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d%d",&left[i],&right[i]);
left[i]--;
right[i]--;
}
while(1){
gets(s);
if (strcmp(s,"#End Input#")==0) break;
}
while(1){
gets(s);
if (strcmp(s,"#Start Programmer's Output#")==0) break;
}
gets(s);
if (strcmp(s,"#End Programmer's Output#")==0){
printf("Wrong\n");
continue;
}
gets(ss);
if (strcmp(ss,"#End Programmer's Output#")==0){
if (solve()) printf("Accepted\n");
else printf("Wrong\n");
}else{
printf("Wrong\n");
}
while(1){
if (strcmp(ss,"#End Programmer's Output#")==0) break;
gets(ss);
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator