几个相似的DP题

　　HDU1398

　　题意：把一个整数分拆成1、4、9、16、……、256、289（注意：只到289）这17个完全平方数的和，有几种方法。

　　解法不用说自然是DP，因为搜索显然超时。

　　（这样的题我一般不敢开int，怕爆……)

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <functional>

 using namespace std;

 #define REP(i,n)        for(int i(0); i <  (n); ++i)

 #define rep(i,a,b)        for(int i(a); i <= (b); ++i)

 #define dec(i,a,b)        for(int i(a); i >= (b); --i)

 #define for_edge(i,x)        for(int i = H[x]; i; i = X[i])

 #define LL    long long

 #define ULL    unsigned long long

 #define MP    make_pair

 #define PB    push_back

 #define FI    first

 #define SE    second

 #define INF    1 << 30

 const int N    =            +    ;

 const int M    =            +    ;

 const int Q    =            +    ;

 const int A    =            +    ;

 LL f[Q];

 int n;

 int main(){

 #ifndef ONLINE_JUDGE

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

     freopen("test.out", "w", stdout);

 #endif

     memset(f, , sizeof f);

     f[] = 1LL;

     rep(i, , ) rep(j, , )

         f[j + i * i] += f[j];

     while (~scanf("%d", &n), n) printf("%lld\n", f[n]);

     return ;

 }

　　HDU1028 自然数无序拆分　　

　　恩，经典的DP题

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <functional>

 using namespace std;

 #define REP(i,n)        for (int i(0); i < (n); ++i)

 #define rep(i, a, b)    for (int i(a); i <= (b); ++i)

 #define dec(i, a, b)    for (int i(a); i >= (b); --i)

 #define LL    long long

 #define ULL   unsigned long long

 #define MP    make_pair

 #define FI    first

 #define SE    second

 const int INF  =    ;

 const int M    =        +    ;

 const int N    =        +    ;

 const int A    =        +    ;

 int f[N][N];

 int n;

 int main(){

     freopen("1test.in", "r", stdin);

     freopen("1test.out", "w", stdout);

     rep(i, , ) f[][i] = , f[i][] = ;

     rep(i, , ) rep(j, , ){

         if (j > i) f[i][j] = f[i][i]; else

         if (i == j) f[i][j] = f[i][j - ] + ; else

         f[i][j] = f[i][j - ] + f[i - j][j];

     }

     while (~scanf("%d ", &n)) printf("%d\n", f[n][n]);

     return ;

 }

　　　二维的方法……但是我以前用一维的方法AC过，总觉得该回忆起来……

　　HDU5890 去掉给定编号的三个数（如果有编号重复那就相当于去掉了两个数甚至一个数）任意选10个数，相加，是否可以得到87？

　　当初青岛网赛的题，题意不难理解就是A不掉。

　　后来查了很多资料，并且看了很多巨屌的博客。我终于得出一个结论：此题要用bitset优化。

　　思想也是背包，但是和前两道比起来就比较复杂了。

#include <bitset>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i,a,b)        for(int i(a); i <= (b); ++i)

#define dec(i,a,b)        for(int i(a); i >= (b); --i)

const int N    =            +    ;

int T;

int q;

int f[N][N][N];

int n;

int c[];

int a[N];

int Q;

bitset <> A[];

int check(int i, int j, int k){

    rep(h, , ) A[h].reset(); A[][] = ;

    rep(h, , n) if (h != i && h != j && h != k && a[h] <= ) dec(p, , ){

        A[p + ] |= A[p] << a[h];

        if (A[][]) return ;

    }

    return ;

}

int main(){

#ifndef ONLINE_JUDGE

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

    freopen("test.out", "w", stdout);

#endif

    scanf("%d", &T);

    while (T--){

        scanf("%d", &n);

        rep(i, , n) scanf("%d", a + i);

        rep(i, , n) rep(j, i, n) rep(k, j, n) f[i][j][k] = check(i, j, k);

        scanf("%d", &Q);

        while (Q--){

            scanf("%d%d%d", c + , c + , c + );

            sort(c + , c + );

            puts(f[c[]][c[]][c[]] ? "Yes" : "No");

        }

    }

    return ;

}

继续努力吧！！

巴特西

几个相似的DP题

最新文章

热门文章