study from:
https://www.cnblogs.com/flashhu/p/9480669.html
1.前缀和
https://www.luogu.org/problemnew/show/P2513
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define E 2.7182818284 23 const int mod=1e4;//998244353 24 const int maxn=1e3+10; 25 26 int f[maxn][maxn],tot[maxn]; 27 28 int main() 29 { 30 int n,k,i,j,l; 31 scanf("%d%d",&n,&k); 32 f[1][0]=1; 33 for (i=2;i<=n;i++) 34 { 35 tot[0]=0; 36 l=min(i*(i-1)/2,k); 37 for (j=0;j<=l;j++) 38 tot[j]=(tot[j-1]+f[i-1][j])%mod; 39 for (j=0;j<=l;j++) 40 f[i][j]=(tot[j]-tot[max(j-i,-1)]+mod)%mod; 41 } 42 printf("%d",f[n][k]); 43 return 0; 44 }
https://www.luogu.org/problemnew/show/P2511
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define E 2.7182818284 23 const int mod=10007;//998244353 24 const int maxn=5e4+10; 25 26 int a[maxn],t[maxn],tot[maxn],f[maxn][2]; 27 28 int main() 29 { 30 int n,c,x,y,i,j,k,l,r,m,result=0; 31 scanf("%d%d",&n,&c); 32 c++; 33 for (i=1;i<=n;i++) 34 scanf("%d",&a[i]); 35 l=1; r=5e7; 36 while (l<=r) 37 { 38 m=(l+r)>>1; 39 j=1; 40 k=0; 41 for (i=1;i<=n;i++) 42 if (a[i]>m) 43 break; 44 else if (k+a[i]>m) 45 { 46 j++; 47 k=a[i]; 48 } 49 else 50 k+=a[i]; 51 if (i==n+1 && j<=c) 52 r=m-1; 53 else 54 l=m+1; 55 } 56 printf("%d ",l); 57 58 t[0]=0; 59 for (i=1;i<=n;i++) 60 t[i]=t[i-1]+a[i]; 61 62 f[0][0]=1; 63 x=1,y=0; 64 for (j=1;j<=c;j++) 65 { 66 tot[-1]=0; 67 for (i=0;i<=n;i++) 68 tot[i]=(tot[i-1]+f[i][y])%mod; 69 //f[i][j] f[][j-1] 70 k=0; 71 f[0][x]=0; 72 for (i=1;i<=n;i++) 73 { 74 //[k,i) 75 while (t[i]-t[k]>l) 76 k++; 77 f[i][x]=(tot[i-1]-tot[k-1])%mod; 78 } 79 result=(result+f[n][x])%mod; 80 x=x^1; 81 y=y^1; 82 } 83 printf("%d",(result+mod)%mod); 84 return 0; 85 } 86 /* 87 5 1 88 3 3 4 5 3 89 90 5 3 91 1 1 1 1 1 92 */
2.单调队列优化
https://www.luogu.org/problemnew/show/P1886
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <time.h> 6 #include <string> 7 #include <set> 8 #include <map> 9 #include <list> 10 #include <stack> 11 #include <queue> 12 #include <vector> 13 #include <bitset> 14 #include <ext/rope> 15 #include <algorithm> 16 #include <iostream> 17 using namespace std; 18 #define ll long long 19 #define minv 1e-6 20 #define inf 1e9 21 #define pi 3.1415926536 22 #define E 2.7182818284 23 const int mod=10007;//998244353 24 const int maxn=1e6+10; 25 26 /** 27 n个数字a[1]-a[n],每个大小为m的区间 28 最小值和最大值 29 **/ 30 31 int a[maxn],x[maxn]; ///x:记录下标 32 33 int main() 34 { 35 int n,m,i,head,tail; 36 scanf("%d%d",&n,&m); 37 for (i=1;i<=n;i++) 38 scanf("%d",&a[i]); 39 ///min 40 head=1,tail=0; 41 ///以i作为末尾的区间 42 for (i=1;i<=n;i++) 43 { 44 45 while (head1<=tail1 && x[head1]<=i-m) 46 head1++; 47 while (head1<=tail1 && a[x[tail1]]>=a[i]) 48 tail1--; 49 50 ///每个点入队列一次，最多出队列一次 51 while (head<=tail && x[head]<=i-m) ///在区间外的数字被剔除,(i-m,i] 52 head++; 53 while (head<=tail && a[x[tail]]>=a[i]) ///求区间最小/大值，对于在前面的数，只有数值小/大于后面才有用，否则从右往左被剔除(符号相反，大于等于/小于等于)，类似单调栈 54 tail--; 55 tail++; 56 x[tail]=i; 57 if (i>=m) 58 printf("%d%c",a[x[head]],i==n?' ':' '); 59 } 60 61 ///max 62 head=1,tail=0; 63 for (i=1;i<=n;i++) 64 { 65 while (head<=tail && x[head]<=i-m) 66 head++; 67 while (head<=tail && a[x[tail]]<=a[i]) 68 tail--; 69 tail++; 70 x[tail]=i; 71 if (i>=m) 72 printf("%d%c",a[x[head]],i==n?' ':' '); 73 } 74 return 0; 75 }