题目:http://acm.hdu.edu.cn/showproblem.php?pid=5230
题意:给定n,c,l,r。求有多少种方法从1~n-1选取任意k数每个数的权重为其下标,使得这些数字之和加上c之后在l,r范围内。
题解:第一反应是计数01包,但是范围给定的n太大,TLE。。。 然后仔细想想,不就是求l~r范围内不重复的整数划分数嘛。
dp[i][j]表示j这个数字,当前的拆分拥有i个拆分数时的方案数。
先考虑允许重复数字 : dp[i][j] = dp[i][j – i] + dp[i – 1][j – 1];
考虑分成两类,
1、dp[i][j – i]:这种拆分方案(拥有i个数字的拆分方案),如果没有1,就比如7 = 3 + 4这样,然后每个数字都加上一,
就变成了9 = 5 + 4。所以dp[2][9]可以由dp[2][7]转化过来。当然7 = 1 + 6也是合法解。
2、dp[i – 1][j – 1]:这种拆分方案有1,比如4 = 3 + 1,那么我可以截去那个1,变成3 = 3,然后加上最后那个1,就变成了
4 = 3 + 1,所以dp[2][4]可以由dp[1][3]转化过来。
这里提供了一种思维–对数字的组合分类以及每个数都+1的状态转移。这里对是否有1存在做了一个分类。仿照这个思想我们去定义新的dp[i][j].
dp[i][j]表示j这个数字,当前的拆分拥有i个不重复拆分数时的方案数。
按照上述的思维:
(a) 当不存在1的时候,dp[i][j]可以由dp[i][j-i]转移而来;
(b) 当存在1的时候,由于dp的定义只存在一个1。那么我们把这个1单独拎出来,然后对剩下的i-1分成j-i组 dp[i][j]=dp[i-1][j-i];
综合上述的两种情况:dp[i][j] = dp[i][j – i] + dp[i – 1][j – i];
当这里,这道题目还是没法ac。。。因为如果我们用普通的方法去求解这个dp,内存吃不住的,用滚动数组优化一下。
(真心不容易,,,还有一些细节要处理)
ac_code:
#include <cstdio>
#include <iostream>
#include <cstring>
#define mt(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
int dp[][];
const int mod=;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,c,l,r;
scanf("%d %d %d %d",&n,&c,&l,&r);
mt(dp);
if(c>r)
{
cout<<<<endl;
continue;
}
dp[][]=;
int L=l-c;
int R=r-c;
int ans= (L==);// 对0的情况做一个特判断
L=max(,L);
//R=max(n-1,R);
int now=;
for(int i=;i*(i+)/ <= max(R,n-);i++)// 个数 由于是从1开始枚举 那么枚举i个数字的和最小为 i*(i+1)/2 还有就是能取的上限也要注意
{
for(int j=i*(i+)/;j<=R;j++) // 分数 同上,从最小的开始,优化
{
dp[now][j]=(dp[now][j-i]+dp[!now][j-i])%mod; // 滚动数组
if(j>=L && j<=R)
{
ans+=dp[now][j];
ans%=mod;
}
}
memset(dp[!now],,sizeof(dp[!now]));
now=!now;
}
printf("%d\n",ans);
}
return ;
}