dp
首先找出最大的回合数,可以由等差数列求和来计算,撑到第k回合需要消耗的体力,记为s[k]。只需找到某个k,使得s[k]<=x+y并且s[k+1]>x+y。
接着我们进行dp,dp[i][j]表示,撑到了第i回合,此时向日葵的体力还剩j。
那么蘑菇的体力还剩多少呢?撑到第i回合,总共消耗的体力为s[i],向日葵的体力消耗为p=x-j,则蘑菇的体力消耗为q=s[i]-p,如果q<=y则说明当前dp[i][j]的状态是可以由这一回合消耗蘑菇i点体力来达到的,则:
dp[i][j]+=dp[i-1][j]
即向日葵不需要消耗体力。另外,当前向日葵的剩余体力为j,如果这一回合消耗的是向日葵的体力,那么上一回合,向日葵的体力剩余值应该为i+j,如果i+j<=x说明是合法状态,此时:
dp[i][j]+=dp[i-1][j+i]
至此,状态转移分析完成。那么初始状态呢?初始状态为,当前撑过了0回合,且向日葵的体力剩余为x,此时的方案数为1,即:
dp[0][x]=1
时间复杂度分析:
我们需要求出每一个状态的方案数,最大回合数约为sqrt(2*(x+y)),向日葵最大剩余体力数为x,因此整个算法的时间复杂度约为 O(N√N)。
但是,我们的空间复杂度时分危险,亲测如果不加降维优化的话,会爆空间,为了便于理解,放上朴素版的dp代码:
#include<bits/stdc++.h>
using namespace std;
const int N=640,M=2e5+10,mod=1e9+7;
int x,y;
int dp[M];//dp[i][j]表示:撑到了第i回合,当前向日葵的体力值为j的所有合法方案
int s[N];
int main(){
cin>>x>>y;
for(int i=0;i<N;i++)s[i]=s[i-1]+i;//等差数列求和
dp[x]=1;
int last,res=0;
for(int i=1;i<N;i++){
last=res,res=0;
for(int j=0;j<=x;j++){
int p=x-j;//向日葵的使用数量
int q=s[i]-p;//蘑菇的使用数量
if(q<=y)dp[j]=dp[j];//这一步可以使用蘑菇
else dp[j]=0;
if(j+i<=x)dp[j]=(dp[j]+dp[j+i])%mod; //这一步可以使用向日葵
res=(res+dp[j])%mod;
}
if(res==0)break;
}
cout<<last<<endl;
return 0;
}
我们可以发现,由于dp[i][j]只能由dp[i-1][j]或者dp[i-1][j+i]转移过来,因此我们可以去掉第一维,并且需要注意的是,我们更新j的值所用到的是上一层大于等于j的状态(j,j+i),因此我们需要从小到大枚举j,这样就能保证用来更新当前层的都是上一层还未被更新的状态。
降维优化的代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1000,M=2e5+10,mod=1e9+7;
int x,y;
//由于dp[i][j]只能由dp[i-1][...]转移而来,因此可以加入降维优化
int dp[M];//dp[i][j]表示:撑到了第i回合,当前向日葵的体力值为j的所有合法方案
int s[N];
int main(){
cin>>x>>y;
for(int i=0;i<N;i++)s[i]=s[i-1]+i;//等差数列求和
int k=0;//找到能撑住的最大回合
for(int i=0;i<N;i++){
if(s[i]>x+y)break;
k=i;
}
dp[x]=1;
int last,res=0;
for(int i=1;i<=k;i++){
for(int j=0;j<=x;j++){
int p=x-j;//向日葵的使用数量
int q=s[i]-p;//蘑菇的使用数量
if(q<=y)dp[j]=dp[j];//这一步可以使用蘑菇
else dp[j]=0;//这一步不能使用蘑菇
if(j+i<=x)dp[j]=(dp[j]+dp[j+i])%mod; //这一步可以使用向日葵
}
}
for(int i=0;i<=x;i++)res=(res+dp[i])%mod;
cout<<res<<endl;
return 0;
}