hdu1028 Ignatius and the Princess III && hdu2082 找单词 && poj1664 放苹果 && noj1046 正整数划分问题——整数划分

May 12, 2013
Hdu

这种问题有两种做法，DP和母函数。 hdu1028 Ignatius and the Princess III 题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1028 DP做法：


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu1028.in", "r", stdin);
#endif
  int i, j, dp[121][121], n;
  dp[1][1] = 1; // WA!
  for (i = 2; i < 121; ++i) {
    dp[i][1] = dp[1][i] = 1;
    for (j = 2; j < 121; ++j) {
      if (i > j) dp[i][j] = dp[i-j][j] + dp[i][j-1];
      else if (i == j) dp[i][j] = dp[i][j-1] + 1;
      else dp[i][j] = dp[i][i];
    }
  }
  while (~scanf("%d", &n)) {
    printf("%d\n", dp[n][n]);
  }

  return 0;
}

母函数做法：


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int a[121], b[121];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu1028.in", "r", stdin);
#endif
  int n;
  while (~scanf("%d", &n)) {
    int i, j, k;
    for (i = 0; i <= n; ++i) a[i] = b[i] = 0;
    a[0] = 1;
    for (i = 1; i <= n; ++i) {
      for (j = 0; j <= n; ++j) {
        for (k = 0; k*i+j <= n; ++k) {
          b[k*i+j] += a[j];
        }
      }
      for (j = 0; j <= n; ++j) {
        a[j] = b[j]; b[j] = 0;
      }
    }
    printf("%d\n", a[n]);
  }

  return 0;
}

hdu2082 找单词题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2082 只写了母函数的。因为这个有个数限制。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int a[51], b[51];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu2082.in", "r", stdin);
#endif
  int t; scanf("%d", &t);
  while (t--) {
    int i, j, k, num;
    for (i = 0; i <= 50; ++i) {
      a[i] = b[i] = 0;
    }
    a[0] = 1;
    for (i = 1; i <= 26; ++i) {
      scanf("%d", &num);
      for (j = 0; j <= 50; ++j) {
        for (k = 0; k <= num && k*i+j <= 50; ++k) {
          b[k*i+j] += a[j];
        }
      }
      for (j = 0; j <= 50; ++j) {
        a[j] = b[j]; b[j] = 0;
      }
    }
    int sum = 0;
    for (i = 1; i <= 50; ++i) sum += a[i];
    printf("%d\n", sum);
  }

  return 0;
}

poj1664 放苹果题目链接：http://poj.org/problem?id=1664 这道也只写了DP的，用DP处理比较方便。


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("poj1664.in", "r", stdin);
#endif
  int t, n, m; scanf("%d", &t);
  int dp[11][11], i, j;
  dp[1][1] = 1;
  for (i = 2; i < 11; ++i) {
    dp[i][1] = dp[1][i] = 1;
    for (j = 2; j < 11; ++j) {
      if (i > j) dp[i][j] = dp[i][j-1] + dp[i-j][j];
      else if (i == j) dp[i][j] = dp[i][j-1] + 1;
      else dp[i][j] = dp[i][i];
    }
  }
  while (t--) {
    scanf("%d%d", &m, &n);
    printf("%d\n", dp[m][n]);
  }

  return 0;
}

noj1046 正整数划分问题题目链接：http://acm.nankai.edu.cn/p1046.html 跟hdu1028一样一样的……其实就是一道题目o(╯□╰)o


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu1028.in", "r", stdin);
#endif
  int i, j, dp[121][121], n;
  dp[1][1] = 1; // WA!
  for (i = 2; i < 121; ++i) {
    dp[i][1] = dp[1][i] = 1;
    for (j = 2; j < 121; ++j) {
      if (i > j) dp[i][j] = dp[i-j][j] + dp[i][j-1];
      else if (i == j) dp[i][j] = dp[i][j-1] + 1;
      else dp[i][j] = dp[i][i];
    }
  }
  while (~scanf("%d", &n)) {
    printf("%d\n", dp[n][n]);
  }

  return 0;
}

感觉这些基础的东西现在都不熟练……

哈哈，附上一首超级好听的钢琴曲~ 某青推荐的……THX~

Read more