Ural 1696 - Salary for Robots（dp+二位前缀和优化）

题目戳这里

题意：在PTZZZ星球上有$n$个机器人，每个都有一个编号，从$1$到$n$。现在要给他们发工资，每月发一次，每个机器人得到的工资都是不超过$k$的正整数，并且不能存在三个机器人$a$,$b$,$c$，满足$a$的编号大于$b$，$b$的编号大于$c$，$a$的工资小于$b$，$b$的工资小于$c$。现在要求每两个月发工资的情况不能完全相同。PTZZZ星球上有$p$个月，记第一个发工资的月份为第$1$年的$1$月，问你到几月就没法发工资了。

思路：题意可以转化为有多少个长度为$n$的数组，数组中每一个元素都在$[1,k]$中，并且不存在长度为$3$的严格单调递减子序列，求有多少个这样的数组模$p$再加$1$。

我们可以考虑$dp$，设$d{p}_{i,s,t}$为当前将前$i$个元素赋上值，最大值为$s$，能与$s$构成长度为$2$的严格单调递减子序列的最大值为$t$的方案数。

转移方程：
$d{p}_{i,s,t}={\sum }_{p=t+1}^{s}d{p}_{i-1,p,t}+{\sum }_{p=0}^{t}d{p}_{i-1,s,p}(t̸=0)$
$d{p}_{i,s,t}={\sum }_{p=t+1}^{s}d{p}_{i-1,p,t}(t=0)$

这样我们就有了优秀的$O(n{k}^3)$的做法。

$Code:$

#include <bits/stdc++.h>
using namespace std;
int n,k,mod,ans;
int dp[1005][205][205];
int main(){
scanf("%d%d%d",&n,&k,&mod);
for(int i=1;i<=k;i++)	dp[1][i][0]=1;
for(int i=2;i<=n;i++){
for(int s=1;s<=k;s++){
for(int t=s-1;t>=0;t--){
for(int p=t+1;p<=s;p++)
dp[i][s][t]=(dp[i][s][t]+dp[i-1][p][t])%mod;
if(t)
for(int p=0;p<=t;p++)
dp[i][s][t]=(dp[i][s][t]+dp[i-1][s][p])%mod;
}
}
}
for(int i=1;i<=k;i++)	for(int j=0;j<i;j++)	ans=(ans+dp[n][i][j])%mod;
cout<<ans+1<<endl;
}

然而，我们发现这样子是过不去的，因此我们可以考虑优化。我们不难发现转移方程里的$d{p}_{i-1,p,t}$与$d{p}_{i-1,s,p}$中都有一维与$d{p}_{i,s,t}$相同，因此我们可以考虑二维前缀和，这样复杂度就降到了$O(n{k}^2)$。

$Code:$

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,mod,ans;
int dp[205][205],sum[205][205];
signed main(){
scanf("%I64d%I64d%I64d",&n,&k,&mod);
for(int i=0;i<=k;i++)	dp[i][0]=sum[i][0]=1;
for(int i=2;i<=n;i++){
memset(dp,0,sizeof(dp));
for(int s=1;s<=k;s++){
for(int t=s-1;t>=0;t--)
sum[s][t]=(sum[s][t]+sum[s][t+1])%mod;
for(int t=0;t<s;t++)
sum[s][t]=(sum[s][t]+sum[s-1][t])%mod;
}
for(int s=1;s<=k;s++){
for(int t=0;t<s;t++){
dp[s][t]=(sum[s][t]-sum[s][t+1]-sum[t][t]+sum[t][t+1]+mod*12345)%mod;
if(t)
dp[s][t]=(dp[s][t]+sum[s][0]-sum[s-1][0]-sum[s][t+1]+sum[s-1][t+1]+mod*12345)%mod;
}
}
memset(sum,0,sizeof(sum));
for(int s=1;s<=k;s++)
for(int t=0;t<s;t++)
sum[s][t]=dp[s][t];
}
for(int i=1;i<=k;i++)	for(int j=0;j<i;j++)	ans=(ans+dp[i][j])%mod;
cout<<ans+1<<endl;
}

据某位大神说还有更高效的$O(nklogk)$的算法，使用数据结构再次优化，但是蒟蒻不会，因此这里就不贴了。有兴趣的思考一下，然后在下面评论哦。

最后

以上就是大胆菠萝为你收集整理的Ural 1696 - Salary for Robots（dp+二位前缀和优化）的全部内容，希望文章能够帮你解决Ural 1696 - Salary for Robots（dp+二位前缀和优化）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。