hdu 4669 动态规划
2024-08-25 01:27:45
思路:主要就是一个动态方程dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];我用的是滚动数组。其实也就是dp[i][(j*Exp[len[num[i]]]+num[i])%k]+=dp[i-1][j];
唯一需要注意的就是存在长度长于n的串,要减掉。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define Maxn 100010
using namespace std;
int len[Maxn],Exp[Maxn*],n,k,num[Maxn];
int dp[][];
void init()
{
int i;
for(i=;i<;i++) len[i]=;
for(i=;i<;i++) len[i]=;
for(i=;i<;i++) len[i]=;
for(i=;i<=;i++) len[i]=;
}
int main()
{
int i,j;
init();
//freopen("ans.txt","r",stdin);
//freopen("ABCd.txt","w",stdout);
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(dp,,sizeof(dp));
Exp[]=;
for(i=;i<=*n;i++)
Exp[i]=(Exp[i-]*)%k;
for(i=;i<=n;i++)
scanf("%d",num+i);
int sum=,s=;
int ans=;
int pre=,now=;
for(i=;i<=n;i++)
{
now=!now;
pre=!pre;
memset(dp[now],,sizeof(dp[now]));
for(j=;j<k;j++)
dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];
dp[now][num[i]%k]++;
sum=(sum*Exp[len[num[i]]]+num[i])%k;
s+=len[num[i]];
ans+=dp[now][];
}
for(i=;i<n;i++)
{
now=!now;
pre=!pre;
memset(dp[now],,sizeof(dp[now]));
for(j=;j<k;j++)
dp[now][(j*Exp[len[num[i]]]+num[i])%k]+=dp[pre][j];
sum=(sum*Exp[len[num[i]]]+num[i])%k;
dp[now][sum]--;
sum=((sum-num[i]*Exp[s])%k+k)%k;
ans+=dp[now][];
}
printf("%d\n",ans);
}
return ;
}
最新文章
- 最完美解决方案:js弹出窗口关闭当前页面,而不弹出提示框
- nginx反向代理编译异常
- 2227 邮票--FUoj(链接表+树的直径)
- Android EditText内容监听
- I’m stuck!(BFS)
- java生产随机字符串
- vsftp快速配置
- js_sl 分享
- MJ刷新控件MJRefreshFooterView上拉之后收不回来的解决办法
- bzoj 3675 [Apio2014]序列分割(斜率DP)
- PL/SQL — 隐式游标
- zabbix 启用分区表后需要关闭Housekeeper
- Ubuntu下装QQ2014(http://my.oschina.net/oscfox/blog/315951)
- oracle的知识点总结
- 负载均衡(Load Balancing)学习笔记(三)
- openstack网络基础
- [vue]vue-book
- Python开发【数据结构】:排序练习
- C# 6.0可能的新特性及C#发展历程[转]
- c# byte转docx