poj3181 Dollar Dayz ——完全背包

时间：2022-07-22 16:02:05

link:http://poj.org/problem?id=3181

本来很常规的一道完全背包，比较有意思的一点是，结果会超int，更有意思的解决方法是，不用高精度，用两个整型的拼接起来就行了。ORZ

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <cctype>

 #include <algorithm>

 #include <queue>

 #include <deque>

 #include <queue>

 #include <list>

 #include <map>

 #include <set>

 #include <vector>

 #include <utility>

 #include <functional>

 #include <fstream>

 #include <iomanip>

 #include <sstream>

 #include <numeric>

 #include <cassert>

 #include <ctime>

 #include <iterator>

 const int INF = 0x3f3f3f3f;

 const int dir[][] = {{-,},{,},{,-},{,},{-,-},{-,},{,-},{,}};

 using namespace std;

 typedef  unsigned long long ULL;

 ULL dp[], dp1[];

 int main(void) {

     ios::sync_with_stdio(false);

 #ifndef ONLINE_JUDGE

     freopen("in.txt", "r",stdin);

 #endif

     ULL tmp = ;

     for (int i = ; i < ; ++i) tmp*=;

     int n, k;

     while (cin>>n>>k) {

         memset(dp,,sizeof(dp));

         memset(dp1,,sizeof(dp1));

         dp[] = ;

         for (int i = ; i <= k; ++i) {

             for (int j=i; j<= n; ++j) {

                 dp1[j] += (dp1[j-i] + (dp[j]+dp[j-i])/tmp);

                 dp[j] = (dp[j]+dp[j-i])%tmp;

             }

         }

         if (dp1[n]) cout<<dp1[n];

         cout<<dp[n]<<endl;

     }

     return ;

 }

o(╯□╰)o

相关文章