| |
不指定 类别: 数据结构和算法 » WOJ | 吴豪 @ 2009/12/03 02:28 | 评论(2) | 阅读(16941)
【题目大意】
        给出N个正整数,若将其分成三组,每组的和作为三角形一条边的长度,能得到多少种合法的三角形。
        (N<=200,N个数的和Sum不超过600)

【题目分析】
        这题应该不难想到可以递推来做。
        F[i,j,k]表示前i个整数能否凑出一个边长分别为j,k,Sum-j-k的三角形,那么有递推式:
              F[i,j,k] = F[i-1,j,k] or F[i-1,j-Li,k] or F[i-1,j,k-Li]
        这个题时限比较紧,而上面这个递推复杂度是O(NSum^2),很容易超时,所以得注意一下常数优化,核心代码如下:

        F[0][0][0] = 1;
        int Cnt = 0;
        for(int i=1;i<=N;i++)
        {
            int L;
            int Cur = i&1 , Pre = (i-1)&1;
            scanf("%d",&L);
            Cnt += L;
            memset(F[Cur],0,sizeof(F[Cur]));
            for(int j=0;j<=Cnt;j++)
                for(int k=0;k<=Cnt-j;k++)
                {
                        if(F[Pre][j][k])
                        {
                            F[Cur][j][k] = 1;
                            continue;
                        }
                        if(j >= L)
                            if(F[Pre][j-L][k])
                            {
                                F[Cur][j][k] = 1;
                                continue;
                            }
                        if(k >= L)
                            if(F[Pre][j][k-L])
                            {
                                F[Cur][j][k] = 1;
                                continue;
                            }
                }
        }

        做完上面这个递推,我们只需要枚举目标三角形两条边的长度,对于合法的目标三角形利用递推出的F判断其是否可以得到,统计即可。
      

--
hi, 如果还有什么问题,请在下面留言让我们知道 :)
无觅相关文章插件
数据结构和算法 » WOJ | 引用(0) |
2010301500143 Email
2013/03/25 22:14
三维数组会超出内存啊cry
那谁
2012/05/26 01:19
三维数组会超出内存啊
分页: 1/1 第一页 1 最后页