【bzoj1925】地精部落[SDOI2010](dp)
题目传送门:1925: [Sdoi2010]地精部落
这道题,,,首先可以一眼看出他是要我们求由1~n的排列组成,并且抖来抖去的序列的方案数。然后再看一眼数据范围,,,似乎是O(n^2)的dp?然后各种撕烤,,,然而还是不会。。。
对于这道题,我第一眼的想法是用f[i][j]表示长度为i,最后一个数是j的抖动序列的方案数,然而这是个1~n的排列,似乎没法解决数字重复的问题。。QAQ
于是看了一波题解,,,原来这个dp是这样子搞的:用f[i][j]表示i个数的排列、第一个数<=j且开头下降的抖动序列的方案数。
然后dp方程就变成了这样:f[i][j]=f[i][j-1]+f[i-1][i-j]。。。
当开头的数<j(也就是<=j-1)时,抖动序列的方案数显然=f[i][j-1];
当开头的数=j 时,我萌尝试把开头的j删掉,然后再把剩下>j的数统统-1,于是我们就会发现,这时的方案和i-1个数的排列、第一个数<=j-1(因为原序列开头是j,并且开头下降要求原序列的第二个数比j小)且开头上升的抖动序列的方案一一对应。然而这里的开头上升怎么算呢?其实我们发现把一个长度为n、开头下降的序列a[i]的每一位转变为n-a[i]+1,它就变成了一个长度为n、开头上升的抖动序列。所以这时的方案数就=f[i-1][i-j];
所以就可以愉快的dp辣!
代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
int f[][]={};
int n,mod;
int main()
{
int i,j;
scanf("%d%d",&n,&mod);
f[][]=;
for(i=;i<=n;i++)
for(j=;j<=i;j++)
f[i&][j]=(f[i&][j-]+f[(i&)^][i-j])%mod;
printf("%d\n",f[n&][n]*%mod);
}
短得让人心头一震
=========================================2017.8.29更新线=============================================
首先感谢楼下评论@happy_codes。
我看了评论,发现上面的说法确实有点问题,我自己也不知道怎么解释,网上的题解(我目前找到的)也没有说明。这个问题就是:如果(i-1)-x+1<=j-1那么应该得出x>=i-j+1,然而我并不知道为什么这样写答案是对的。。。
但是我还想到了一种写法,f[i][j]表示i个数的排列,第一个数=j且开头下降的方案数,并且用g数组来表示f数组的前缀和:g[i][j]=sigma(f[i-1][k]) (1<=k<=j),然后仿照上面的方法就能列出dp方程
代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
int f[][]={},g[][]={};
int n,mod;
int main()
{
int i,j;
scanf("%d%d",&n,&mod);
f[][]=;
for(i=;i<=n;i++)g[][i]=;
for(i=;i<=n;i++)
for(j=;j<=i;j++){
f[i&][j]=(g[(i&)^][i-]-g[(i&)^][i-j]+mod)%mod;
g[i&][j]=(g[i&][j-]+f[i&][j])%mod;
}
printf("%d\n",g[n&][n]*%mod);
}
最新文章
- [笔记]linux用户与用户组
- eclipse项目打包
- cefsharp设置网页接受语言Accept-Language
- MongoDB(五)mongo语法和mysql语法对比学习
- nsis制作启动Tomcat服务的exe安装包教程
- Validform自定义提示效果-使用自定义弹出框
- JAVA错误:org.apache.jasper.JasperException: java.lang.ClassCastException:org.apache.catalina.util.DefaultAnnotationProcessor cannot be cast to org.apach
- C++primer中的TextQuery(读取文本)
- Redis安装与调试
- Autolayout的在storyboard警告和错误
- C#在父窗口中调用子窗口的过程(无法访问已释放的对象)异常,不存在从对象类型System.Windows.Forms.DateTimePicker到已知的托管提供程序本机类型的映射。
- OC中文件的操作
- Python作业之工资管理
- 转载泡泡机器人——IMU预积分总结与公式推导2
- (Python3 自定义函数实现数字金字塔 代码
- MyBatis :Insert (返回主键、批量插入)
- springMVC3学习--ModelAndView对象(转)
- 洛谷.4172.[WC2006]水管局长(LCT Kruskal)
- MP4介绍与基本AVC编码(x264)教程
- Java 整体测试重点题 错题积累