UVA10313 Pay the Price （划分型dp）

题目

题意：
给出 (N) , (l_1) , (l_2) , (N) 表示钱的面值，问将N拆分可以有多少种拆分数。
有三种情况：
1，给出 (N)，将 (N) 拆分成面值不超过 (N) 的硬币可以有多少种不同的拆分数。
2，给出 (N) 和 (l_1) ，将 (N) 拆分成面值不超过 (l_1) 的硬币可以有多少种不同的拆分数。
3，给出 (N) 和 (l_1) 和 (l_2)，将 (N) 拆分成面值在 (l_1) 到 (l_2) 范围内的硬币可以有多少种不同的拆分数。

思路：动态规划的思路还是比较明显，但不太好想的就是转移方程，如果用 (dp[ i ][ j ]) 表示将面值为 (i) 拆分成面值不超过 (j) 的硬币可以有多少种拆分。

那么可以用 (dp[ i - j ][ j ]) 表示选择面值为 (j) 的硬币，(dp[ i ][ j - 1 ]) 表示不选择面值为j的硬币。
那么状态转移方程就是： (dp[ i ][ j ] += dp[ i - j ][ j ] + dp[ i ][ j - 1 ])

由于数据给的 (n<=300) 那么可以考虑在读入前进行预处理，读入时就可以进行 (O(1)) 的查询。

另外，本题的输入比较毒瘤，需要注意

#include<stdio.h>
#include<algorithm>
#include<cctype>
using namespace std;
typedef long long ll;
int n;const int MAXN = 305;
ll dp[MAXN][MAXN];

void deal(){
    dp[0][0]=1;
    for(int i=0;i<=300;i++){
        for(int j=1;j<=300;j++){
            if(i-j >= 0)dp[i][j] += dp[i - j][j];
            dp[i][j] += dp[i][j - 1];
        }
    }
}


int main(){
    deal();
    while(~scanf("%d",&n)){
        int a=-1,b=-1;char f = getchar();int ID=0;
        while(f != '
'){
            if(isdigit(f)){
                if(ID==2){if(b==-1) b=0;b = b*10+f-'0';}
                if(ID==1){if(a==-1) a=0;a = a*10+f-'0';}
            }
            if(f == ' ') ID++;
            f=getchar();
        }
        if(a > 300) a = 300;
        if(b > 300) b = 300;
        if(a != -1 && b == -1){
            if(a > 300) a =300;
            printf("%lld
",dp[n][a]);
        }
        else if(a == -1 && b == -1){
            printf("%lld
",dp[n][n]);
        }
        else if(a!=-1 && b!=-1){
            if(a >= 1) printf("%lld
",dp[n][b] - dp[n][a-1]);
            else printf("%lld
",dp[n][b]);
        }
    }
    return 0;
}