PKU3378 Crazy Thairs - 动态规划+树状数组

2024-04-07 18:18
文章标签 动态 规划 数组 树状 crazy thairs pku3378

本文主要是介绍PKU3378 Crazy Thairs - 动态规划+树状数组，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给定一个长度为N的数字序列{ai}，问总共有多少个长度为5的上升子序列。（ai<10^9,N<=50000）

分析：

由于数字范围很大，首先将数字离散化为1~N之间的整数。原a[]数组转换为d[]数组，其中d[i]=j表示a[i]是a[]数组中第j小的数。

可以用动态规划来描述这个算法：

p从0到N，令i=d[p]。f[i][k]表示以数字i为结尾，长度为k的上升序列的个数。

f[i][k]+=∑f[j][k-1]（1<=j<i）

f[i][1]=1

这样的动态转移方程是可以求出正确解的，不过时间复杂度是O(n^2)。

这里可以用到树状数组来优化算法。可以看到在状态转移的时候要求的是1~i-1之间f[j][k-1]的和。正好满足树状数组应用的条件。修改f[i][k]的定义，使得它应用于树状数组。时间复杂度降为O(nlogn)

注意：1，最大的一组数据应该会超int64，所以要用大数计算。2，输入数据中ai可能出现相同元素，要注意处理。

 

  1. /*
  2. PKU3378 Crazy Thairs
  3. */
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  9. #define clr(a) memset(a,0,sizeof(a))
  10. #define int64 bignum_t
  12. #define N 50005
  14. /****************************************************/
  16. #define DIGIT 4 //一个数组元素存放的位数个数
  17. #define DEPTH 10000 //DEPTH = 10DIGIT
  18. #define MAX 30 //数组的长度
  20. typedef int bignum_t[MAX+1];
  22. //赋值 
  23. void value(bignum_t a,char buf[]){
  24.     char ch;
  25.     int i,j;
  26.     memset((void*)a,0,sizeof(bignum_t));
  27.     
  28.     for (a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--)
  29.         ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch;
  30.     for (a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
  31.     for (i=1;i<=a[0];i++)
  32.     for (a[i]=0,j=0;j<DIGIT;j++)
  33.         a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';
  34.     for (;!a[a[0]]&&a[0]>1;a[0]--);
  35. }
  37. //输出
  38. void write(const bignum_t a){
  39.     int i,j;
  40.     for (printf("%d",a[i=a[0]]),i--;i;i--)
  41.     for (j=DEPTH/10;j;j/=10)
  42.         printf("%d",a[i]/j%10);
  43.     puts("");
  44. }
  46. //加法
  47. void add(bignum_t a,const bignum_t b){//高精度数a+b,结果在a中
  48.     int i;
  49.     for (i=1;i<=b[0];i++)
  50.     if ((a[i]+=b[i])>=DEPTH)
  51.     a[i]-=DEPTH,a[i+1]++;
  52.     if (b[0]>=a[0])
  53.     a[0]=b[0];
  54.     else
  55.     for (;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);
  56.     a[0]+=(a[a[0]+1]>0);
  57. }
  59. /********************************************************/
  61. int n,m;
  62. int a[N],b[N],d[N];
  63. int64 f[N][5];
  65. int cmp(const void *i,const void *j){
  66.     return a[*(int*)i]-a[*(int*)j];
  67. }
  69. void Add(int i,int j,int64 t){
  70.     while(i<=m){
  71.         add(f[i][j],t);
  72.         i+=-i&i;
  73.     }
  74. }
  76. void Sum(int i,int j,int64 s){
  77.     char c0[10]="0";
  78.     value(s,c0);
  79.     while(i>0){
  80.         add(s,f[i][j]);
  81.         i-=-i&i;
  82.     }
  83. }
  85. int main()
  86. {
  87.     while(scanf("%d",&n)!=EOF){
  88.         int i,j,k;
  89.         //input
  90.         for(i=0;i<n;i++){
  91.             scanf("%d",&a[i]);
  92.             b[i]=i;
  93.         }
  94.         //order
  95.         qsort(b,n,sizeof(b[0]),cmp);
  96.         m=1;
  97.         d[b[0]]=1;
  98.         for(i=1;i<n;i++){
  99.             if(a[b[i]]!=a[b[i-1]]) m++;
  100.             d[b[i]]=m;
  101.         }
  103.         //DP
  104.         int64 v1,t,u;
  105.         char c0[10]="0";
  106.         char c1[10]="1";
  107.         value(v1,c1);
  108.         for(k=0;k<=m;k++){  //clr
  109.             for(j=0;j<5;j++){
  110.                 value(f[k][j],c0);
  111.             }
  112.         }
  113.         for(k=0;k<n;k++){   //DP
  114.             i=d[k];
  115.             Add(i,0,v1);    //f[i][0]=1
  116.             for(j=1;j<=4;j++){
  117.                 Sum(i-1,j-1,t); //f[][j] t=Sum(i-1)
  118.                 Add(i,j,t); //f[][j] Add(i,t)
  119.             }
  120.         }
  121.         //Total
  122.         int64 total;
  123.         Sum(m,4,total);
  124.         //output
  125.         write(total);
  126.     }
  127.     return 0;
  128. }

这篇关于PKU3378 Crazy Thairs - 动态规划+树状数组的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/883323。

相关文章

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始，按照书籍的划分，第10章开始就进入保护模式（Protected Mode）部分了，感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断（Interrupt）的设计，中断的几种方式：外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用： 为了更好的利用处理器的性能。协同快速和慢速设备一起工作
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
动态规划---打家劫舍

动态规划---打家劫舍

题目： 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 思路： 动态规划五部曲： 1.确定dp数组及含义 dp数组是一维数组，dp[i]代表
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
软考系统规划与管理师考试证书含金量高吗？

软考系统规划与管理师考试证书含金量高吗？

2024年软考系统规划与管理师考试报名时间节点： 报名时间：2024年上半年软考将于3月中旬陆续开始报名 考试时间：上半年5月25日到28日，下半年11月9日到12日 分数线：所有科目成绩均须达到45分以上（包括45分）方可通过考试 成绩查询：可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间：预计在11月左右 证书领取时间：一般在考试成绩公布后3~4个月，各地领取时间有所不同
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
代码随想录冲冲冲 Day39 动态规划Part7

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d
阅读更多...
数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2