nbu 2412 Dice（未AC，但是AC了源出处，LightOJ 1193） - c++编程基础

题目大意：

有N个骰子，每个骰子有K个面，分别标号1~K，设每个骰子向上的面的值为fi，如果sum(fi)等于S，那么获得一个分数sco=mult(fi)。

sum(fi)=f1+f2+...+fn

mul(fi)=f1*f2*...*fn

求所有mul(fi)的和。

时间限制为2s

N (1 ≤ N ≤ 1000) K (1 ≤ K ≤ 1000) S (0 ≤ S ≤ 15000).

题目思路：

要求所有N个骰子的sum(fi)为S的所有mul(fi)的和，设为ans[n][s]。

显然有ans[n][s]=ans[n-1][s-1]+2*ans[n-1][s-2]+...+k*ans[n-1][s-k]

可以把上式作为状态转移方程：

dp[i][j] = dp[i-1][j-1] + 2*dp[i-1][j-2] + ... + k*dp[i-1][j-k]

如果用该转移方程，不难判断复杂度为O(n*k*s)，肯定是超时的。

其实我们仔细观察转移方程的右边可以看成：

= dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-k]

+ dp[i-1][j-2] + dp[i-1][j-3] + ... + dp[i-1][j-k]

+ dp[i-1][j-k]

我们设sum[i][j] = dp[i][j-1] + dp[i][j-2] + ... + dp[i][1]

那么转移方程的右边又可以看成：

= sum[i-1][j-1] - sum[i-1][j-k-1]

+ sum[i-1][j-2] - sum[i-1][j-k-1]

+ sum[i-1][j-k] - sum[i-1][j-k-1]

我们再设ssum[i][j] = sum[i][j] + sum[i][j-1] + ... + sum[i][1]

这样转移方程的右边又可以看成

= ssum[i][j-1] - ssum[i][j-k-1] - k*sum[i][j-k-1]

这样我们就把O(k)求dp[i][j]，转为了O(1)，而算法的整体复杂度也降为了O(n*s)，这样就不会超时咯。

但是空间复杂度也是O (n*s)的，但是我们发现，求i只需要知道i-1，所以我们可以用滚动数组来处理，这样空间复杂度就降到了O(2*s)。

需要注意的是j-k-1<1的时候，转移方程略有区别，不过也只是小细节的问题，很容易处理。

代码：

[cpp]
#pragma comment(linker, "/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll __int64
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n))
#define clr_all(x,c) memset(x,c,sizeof(x))
#define IT iterator
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle l+r>>1
#define MOD 100000007
#define inf 0x3f3f3f3f
#define eps (1e-8)
#define PI 3.1415926535897932384626433832795
#define E 2.7182818284590452353602874713527
template T _min(T a,T b){return a template T _max(T a,T b){return a>b a:b;}
template T _abs(T a){return a>0 a:-a;}
template T _mod(T a,T m){return a template T _gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}
template void _swap(T &a,T &b){T t=b;b=a;a=t;}
template void getmax(T &a,T b){a= a>b a:b;}
template void getmin(T &a,T b){a= (a!=-1 && a int TS,cas=1;
const int M=15000+5;
ll n,k,s,m;
ll dp[2][2][M],now,pre,tmp;

void run(){
ll i,j;
scanf("%lld%lld%lld",&n,&k,&s);
now=0;
dp[now][0][0]=dp[now][1][0]=0;
for(i=1;i<=s;i++){
dp[now][0][i]=dp[now][0][i-1]+(i<=k i:0);
dp[now][1][i]=(dp[now][1][i-1]+dp[now][0][i])%MOD;
}
for(i=2;i<=n;i++){
pre=now;
now^=1;
dp[now][0][i-1]=dp[now][1][i-1]=0;
for(j=i;j<=s;j++){
if(j else tmp=((dp[pre][1][j-1]-dp[pre][1][j-k-1]-dp[pre][0][j-k-1]*k)%MOD+MOD)%MOD;
dp[now][0][j]=(dp[now][0][j-1]+tmp)%MOD;
dp[now][1][j]=(dp[now][1][j-1]+dp[now][0][j])%MOD;
}
}
printf("Case %d: %lld\n",cas,((dp[now][0][s]-dp[now][0][s-1])%MOD+MOD)%MOD);
}

void presof(){
}

int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
presof();
//run();
//while(~scanf("%d",&n)) run();
for(scanf("%d",&TS),cas=1;cas<=TS;cas++) run();
return 0;
}