关于DP专题：
这几天主要收获是数位dp和斜率优化的具体模板，期望：
数位dp
dfs(数的最后若干位,各种限制条件,当前第几位)
if 最后一位
return 各种限制条件下的返回值
局部变量 ct=当前位的数字
局部变量 sum=0;
for i=0 to ct-1
sum+=当前位取i时一定无无限制的合法状态数
sum+=当前位取i时满足当前限制的合法状态数
根据ct更新限制条件 不再满足则return sum
return sum+dfs(当前位后的若干位,更新后的限制条件,下一位)
slv(当前数)
if(只有一位) return 对应的贡献
局部变量 ct;
for ct=可能最高位 to 1
if 当前位有数字 break
局部变量 nw=当前位数字
局部变量 sum=0
for i=1 to nw-1
sum+=当前位取i后合法情况任意取的贡献
for i=1 to ct-1
for j=1 to 9
sum+=第i位取j后合法情况任意取的贡献
sum+=dfs(去掉第一位后的若干位,限制条件,第二位)
return sum
main
预处理当前位取i的各种条件各种限制的贡献
读入 L R
--L
输出 slv(R)-slv(L)
return 0
斜率优化：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=50010;
int n,L;
db sum[maxn],dp[maxn];
int head,tail,Q[maxn];
int X(int i){return ...}
int Y(int i){return ...}
int slope(int i,int j){return (Y(i)-Y(j))/(X(i)-X(j));}
int main(){
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++){
scanf("%lf",&sum[i]);
sum[i]+=sum[i-1];
}
head=tail=1;
for(int i=1;i<=n;i++){
while(l<r){
int mid=(l+r)>>1;
if(slope(q[mid],q[mid+1])>k){
l=mid+1;
}else{
r=mid;
}
}
dp[i]=dp[Q[head]]+Y-...*X;
while(head<tail&&slope(i,Q[tail-1])符号slope(Q[tail-1],Q[tail])) --tail;
Q[++tail]=i;
}
printf("%lld\n",(LL)dp[n]);
return 0;
}
期望DP
期望是个神奇的东西，他是连续的，具体来说，要记住这个最重要的公式
\(E(kp)=kE(p)\)
关于比赛
其中我的决策部分在ACM赛制下出现了一些问题，因为ACM只有AC/UAC所以我为了得到这一道题的分数，死磕一道题3h，使得我只做出1道题(还不是正解)。
我对于自己想出的解法不够自信，应该在草稿纸上多尝试一下，不要轻易放弃。
（例如我最开始想出T1的正解，但没考虑清楚就直接否定掉了）
关于合作部分我觉得我和fwj的合作是非常好的，彼此之间足够相信就避免了抢电脑之类的事情发生。
总的来说，ACM赛制会更锻炼我们的思维和能力，逼迫我们想正解。
标签：总结,return,int,sum,当前,dp,ct From： https://www.cnblogs.com/hfjh/p/17090828.html