POJ 3181 Dollar Dayz

举报
Linux猿 发表于 2021/08/05 00:25:24 2021/08/05
【摘要】 题目链接~~> 做题感悟:状态方程很容易推出,但是提交一直wa,换了__int64 也 wa , 就只能高精度了。 解题思路:初始化一定要注意 0 元钱是代表什么也不买,一种方案。               状态方程: dp [ i ...

题目链接~~>

做题感悟:状态方程很容易推出,但是提交一直wa,换了__int64 也 wa , 就只能高精度了。

解题思路:初始化一定要注意 0 元钱是代表什么也不买,一种方案。

              状态方程: dp [ i ] = dp [ i ] + dp [ i - v ] ; 因为高精度的原因最多34位,可以把一个数分解为两个__int64 位的数表示,具体见代码。

代码:


      #include<stdio.h>
      #include<iostream>
      #include<map>
      #include<stack>
      #include<string>
      #include<string.h>
      #include<stdlib.h>
      #include<math.h>
      #include<vector>
      #include<queue>
      #include<algorithm>
      using namespace std ;
      #define lld __int64
      const double PI = 3.1415926 ;
      const double esp = 1e-7 ;
      const int INF = 999999999 ;
      const int MX = 10005 ;
      const lld md = 1000000000000000000 ;
      lld n,k ;
      lld low[MX],hig[MX] ; // hig[] 存高 18 位 ,low[] 存低 18 位
      void DP()
      {
      memset(low,0,sizeof(low)) ;
      memset(hig,0,sizeof(hig)) ;
       low[0]=1 ;
      for(lld i=1 ;i<=k ;i++)
      for(lld j=i ;j<=n ;j++)
       {
       hig[j]=hig[j-i]+hig[j]+(low[j]+low[j-i])/md ;
       low[j]=(low[j]+low[j-i])%md ; // md 相当于 10 进制的 10
       }
      }
      int main()
      {
      while(~scanf("%I64d%I64d",&n,&k))
       {
       DP() ;
      if(hig[n])  printf("%I64d",hig[n]) ; // 注意!!
      printf("%I64d\n",low[n]) ;
       }
      return 0 ;
      }
  
 


 

文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/nyist_zxp/article/details/24370049

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。