hdu1028 Ignatius and the Princess III ——DP

May 23, 2013
Hdu DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1028 题目大意：　　　整数拆分，给一个整数n,求它有多少种拆分方法。题目思路：做法一：　　d[i][j]表示把整数 i 拆成最多 j 个数字所具有的方法数。那么　　if (i >ｊ)　d[i][j] = d[i-j][j] + d[i][j-1]; 意思就是如果i>j，那么有两种方式：一种是先把i里面分理处j个1，然后再把i-j拆成最多i-j个数字；另一种是把i拆分成最多j-1个数字。　　if (i < j) d[i][j] = d[i][i]; 意思就是如果i<j，那么这种情况和把数字i最多拆成i个数字的是一样的。　　if (i == j) d[i][j] = d[i][j-1] + 1; 意思就是如果i==j，那么可以把数字i拆分成j-1个数字，也可以把数字i拆分成i个1（这个就是那个1的意义）


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define LL long long
int d[140][140], n;
void init() {
  while (~scanf("%d", &n)) {
    int i, j; memset(d, 0, sizeof(d));
    for  (i = 0; i <= n; ++i) d[i][1] = d[1][i] = 1;
    for (i = 2; i <= n; ++i) {
      for (j = 1; j <= n; ++j) {
        if (i > j) d[i][j] = d[i-j][j] + d[i][j-1];
        else if (i == j) d[i][j] = 1 + d[i][j-1];
        else d[i][j] = d[i][i];
      }
    }
    cout << d[n][n] << endl;
  }
}
int main(void) {
  init();
  return 0 ;
}

　　剩下的就是考虑一下边界，比如当 i 或者 j 等于1的时候，显然都是只有一种拆分情况。做法二：　　借用hdu1284这道题的方法，也可以做这道题目，因为n的范围是120嘛,两个算法的复杂度都是O(n^2)的，当然可以了。只需要把hdu1284的代码里面把3改成n，这题就过了……


#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAX = 32768+10;
long long d[MAX];
void solve() {
  int n, i, j;
  while (~scanf("%d", &n)) {
    memset(d, 0, sizeof(d));
    d[0] = 1;
    for (i = 1; i <= n; ++i) {
      for (j = i; j <= n; ++j) {
        d[j] += d[j-i];
      }
    }
    printf("%lld\n", d[n]);
  }
}
int main(void) {
  solve();
  return 0;
}

优化到了一维数组，这个方法碉堡了…… 参考博客：http://www.cnblogs.com/qiufeihai/archive/2012/09/11/2680840.html 膜拜……

Read more