P1048 送给圣诞夜的贺卡

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100],b[100][100],c[100][100],l[100],n,ans=0;
int kesou[100][100],t[100],ttt[100],xxxx=-59;
 
void dfs(int x,int v[],int xxx)
{
   int r[100],hh[100];
   int u[100];
   if(xxx>ans) ans=xxx;
   if(xxx+ttt[x]<ans) xxxx=1;
   else
   {
       for(int i=x+1;i<=n;i++) r[i]=i;
       for(int i=x+1;i<=n;i++) hh[i]=a[i]; 
       for(int i=x+1;i<=n-1;i++)
       {
          for(int j=i+1;j<=n;j++)
          {
              if(hh[i]<hh[j])
              {
                 swap(hh[i],hh[j]);
                 swap(r[i],r[j]);
              }      
          }
       }
       int kfen=x+1;
       for(int i=r[kfen];kfen<=n;i=r[++kfen])
       {
          if(v[i]==0&&i>x)
          {
             for(int j=1;j<=n;j++) u[j]=v[j];
             for(int j=1;j<=l[i];j++)
             {
                if(c[i][j]>x) u[c[i][j]]=1;
             }
             u[i]=1;
             dfs(i,u,xxx+a[i]);
          }
       }
   }
}
int main()
{
   int x,y,v[100];
   int r[100],hh[100];
   memset(v,0,sizeof(v));
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
   {
      scanf("%d",&a[i]);        
   }
   while(scanf("%d%d",&x,&y)!=EOF)
   {
      b[x][y]=1;
      b[y][x]=1;                      
   }
   for(int i=n-1;i>=1;i--)
      ttt[i]=ttt[i+1]+a[i+1];
   for(int i=1;i<=n;i++)
   {
      for(int j=1;j<=n;j++)
      {
         if(b[i][j]==1)
         {
            l[i]++;
            c[i][l[i]]=j;              
         }
      }
   }
   for(int i=1;i<=n;i++) r[i]=i;
   for(int i=1;i<=n;i++) hh[i]=a[i]; 
   for(int i=1;i<=n-1;i++)
   {
      for(int j=i+1;j<=n;j++)
      {
          if(hh[i]<hh[j])
          {
             swap(hh[i],hh[j]);
             swap(r[i],r[j]);
          }      
      }
   }
   int kfen=1;
   //for(int i=1;i<=n;i++) printf(" %d",r[i]);
   for(int i=r[1];kfen<=n;i=r[++kfen])
   {
      for(int j=1;j<=l[i];j++)
      {
            v[c[i][j]]=1;     
      }
      v[i]=1;
      dfs(i,v,a[i]);
      memset(v,0,sizeof(v));
   }
   printf("%d",ans);
   system("pause");
   return 0;
} 

谁能告诉我,我这代码还能怎么优化

兴华神将0

当前位置:/home/记录/详细个人通过/递交:11/73(15%)
P1048送给圣诞夜的贺卡Time Exceeded
记录信息
评测状态 Time Limit Exceeded
题目 P1048 送给圣诞夜的贺卡
递交时间 2014-04-29 19:03:19
代码语言 C++
评测机 VijosEx
消耗时间 3541 ms
消耗内存 624 KiB
评测时间 2014-04-29 19:03:22
评测结果
编译成功

测试数据 #0: TimeLimitExceeded, time = 1014 ms, mem = 576 KiB, score = 0
测试数据 #1: Accepted, time = 0 ms, mem = 568 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 564 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 624 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 572 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 576 KiB, score = 10
测试数据 #7: Accepted, time = 499 ms, mem = 580 KiB, score = 10
测试数据 #8: TimeLimitExceeded, time = 1014 ms, mem = 576 KiB, score = 0
测试数据 #9: TimeLimitExceeded, time = 1014 ms, mem = 576 KiB, score = 0
TimeLimitExceeded, time = 3541 ms, mem = 624 KiB, score = 70

1 条评论

  • 1

信息

ID
1048
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
2329
已通过
401
通过率
17%
被复制
7
上传者