acm 里硬币问题 具体题目见下，采用穷举法时间超限，请问怎么修改

主页 讨论版 问题 名次 状态 统计
问题 L: 还是硬币问题
时间限制: 1 Sec 内存限制: 128 MB
提交: 183 解决: 30
状态
题目描述
给你无限多个1元的硬币和2元的硬币，还有5元的硬币。

现在要你从这3种硬币中取n个硬币，使得他们的价值和为m

输入
多组输入

每组n ， m

n < 1e6 , m <1e6

输出
总的方案数目

样例输入
2 3
样例输出
1

#include
int main()
{
int n,m;
int x,y,z,i,k,j;
i=0;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(x=0; x<=n; x++)
{
for(y=0; y<=n-x; y++)
{
for(z=0; z<=n-x-y; z++)
{
if((x+y+z==n)&&(x+2*y+5*z==m))
{
i++;
}

            }
        }
    }
    printf("%d\n",i);
}
return 0;

}

假设1元，2元，5元硬币分别为a,b,c个

求满足约束条件
a + b + c = n            (1)         
的情况下，
a + 2*b + 5*c = m    (2)
解的个数。

直接用(1) - (2), 得到公式(3)

 b + 4c = m-n        (3)
 a被消去了，因为
 0 <= a <= n
 所以约束条件变为,
 0 <= b + c <= n

最终就变成了求
b+4c = m - n
有多少组整数解的问题

int resolve(int n, int m) {
    int b = 0, c = 0;
    int temp = m - n;
    int sum = 0;

    if ((temp % 4) > n) return 0;

    for (int c = (temp/4); c >= 0; --c) {
        b = temp - (c * 4);
        if (b + c <= n)
            sum += 1;
        else
            break;
    }

    return sum;

}

思路大概这样，代码随手写得...

整数拆分问题，可以采用五边形数定理和母函数方法进行计算，详情参见我的博客：http://blog.csdn.net/u011889952/article/details/44813593

我第一时间想到了DP

if (m < n)
return 0;
if (m == n)
return 1;
int temp = m - n;
int count = temp / 4;
count++;
return count;

我来膜拜下大神的风采。。