现在的位置: 首页 > 综合 > 正文

2012ACM ICPC长春现场赛H Math Magic

2013年09月10日 ⁄ 综合 ⁄ 共 1783字 ⁄ 字号 评论关闭

   这个题真是坑啊,到现在为止我都不知道为什么有个地方加了会错,以个人看绝对不会错,就是注释部分,比总和大的因子不可能出现,所以可以省略不要,为什么省略了就会错,我一天的时间砸在上面砸出这么个破结论,不知道acm的严密性哪儿去了

哎,代码发这里,大神们谁能解决我的问题

我刚开始也是看别人的解题报告,都说裸dp,对于我们这些xx们,还是清楚点好;

滚动dp【i%2】【j】【k】,array里面存了公倍数的因子,pos【1001】里面存了某个因子在array中哪个位子

那么dp【i%2】【j】【k】,的意思就是前i个数的和为j,公倍数为第k个位子中的因子(因为这些子公倍数都会是总公倍数的因子,自己都糊涂了,呵呵,希望大家好好理解)

而刚好有了dp的一个重要性质,后面的抉择只与前面的结果有关,与前面的抉择无关,刚好有了和j,公倍数k,就可以用后面的抉择以此算出和跟公倍数,因此形成递推关系

 

 

还有个小技巧就是预处理lcm最小公倍数,否则超时,哎,不得不感叹现场赛卡得紧啊

 

也有一些小感受吧,如果感觉算法时间内能过,尽量多找地方优化,比如这个题目的公倍数都是总公倍数的因子(虽然不这样,算法也只算那么多次,但开的数组就大很多,初始化也就浪费了很多时间,这是今天最大的收获),%2变成&2位运算优化,memset初始化优化

#include <iostream>
#include<stdio.h>
#include<string.h>
#define INF 1000000007
using namespace std;
int n,m,k;
int dp[2][1005][105];
int array[1005],anum,LCM[1005][1005],pos[1005];
int gcd(int a,int b)
{
    int max,min;
    if(a>b)
  max=a;
    else
  max=b;
    min=a+b-max;
    if(max%min==0)
  return min;
    return gcd(min,max%min);
}
int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}
int main()
{
    int i,j,q,p,s,l,pp;
 for(i=1;i<=1000;i++)
  for(j=i;j<=1000;j++)
   LCM[i][j]=LCM[j][i]=lcm(i,j);
    while(scanf("%d%d%d",&m,&k,&n)!=EOF)
    {
  memset(dp,0,sizeof(dp));
        anum=0;
        for(i=1;i<=k;i++)
        {
         //   if(i>m)                              //注释去掉竟然错了,求解释
  //  break;
            if(k%i==0)
            {
                array[++anum]=i;
    pos[i]=anum;
                dp[1%2][i][anum]=1;
            }
        }
        for(q=2;q<=n;q++)
  {
   memset(dp[q&1],0,sizeof(dp[q&1]));
   for(i=1;i<=m;i++)
    for(pp=1;pp<=anum;pp++)
    {
     if(dp[1-q&1][i][pp])
     {
      for(p=1;p<=anum;p++)
      {
       s=i+array[p];
       if(s>m)
        break;
       l=LCM[array[pp]][array[p]];
       dp[q&1][s][pos[l]]+=dp[1-q&1][i][pp];
       while(dp[q&1][s][pos[l]]>=INF)
        dp[q&1][s][pos[l]]-=INF;
      }
     }
    }
  }
        printf("%d\n",dp[n&1][m][pos[k]]);
    }
    return 0;
}

 

 

抱歉!评论已关闭.