最近听说 \(\text{AtCoder}\) 上有个 \(\text{DP26}\) 题挺好的，于是向 @\(\text{SoyTony}\) 要了题单并开始做，希望可以加强我的 DP 能力。
果然我还是爱 DP 的。预计暑假集训结束前正好做完，希望能完成这个 \(\text{flag}\)。
开头的题比较简单，就不写太多了。
2022/08/11。
寒假开始前做完还差不多
其实就剩三个题了，但咕了四个月。2022/12/25
n=rnt(),a[0]=inf;
_for(i,1,n){
a[i]=rnt();
if(i!=1)
f[i]=min(f[i-1]+abs(a[i]-a[i-1]),f[i-2]+abs(a[i]-a[i-2]));
}
printf("%lld\n",f[n]);
n=rnt(),k=rnt();
_for(i,1,n){
a[i]=rnt(),f[i]=i!=1?inf:0;
_for(j,max(1ll,i-k),i-1)
f[i]=min(f[i],f[j]+abs(a[i]-a[j]));
}
printf("%lld\n",f[n]);
n=rnt();
_for(i,1,n){
a[i]=rnt(),b[i]=rnt(),c[i]=rnt();
f[i][0]=max(f[i-1][1],f[i-1][2])+a[i];
f[i][1]=max(f[i-1][0],f[i-1][2])+b[i];
f[i][2]=max(f[i-1][1],f[i-1][0])+c[i];
}
printf("%lld\n",max(f[n][0],max(f[n][1],f[n][2])));
背包板子。
n=rnt(),m=rnt();
_for(i,1,n){
w[i]=rnt(),v[i]=rnt();
for_(j,m,w[i])f[j]=max(f[j],v[i]+f[j-w[i]]);
}
printf("%lld\n",f[m]);
这道题中 \(w\) 很大，我们可以把背包倒着用。
即我们设 \(f_{i,j}\) 表示在前 \(i\) 能选出价值为 \(j\) 的最小体积。
转移方程显然为：
n=rnt(),m=rnt(),f[0]=1;
_for(i,1,1e5)f[i]=inf;
_for(i,1,n){
w[i]=rnt(),v[i]=rnt();
for_(j,1e5,v[i])if(f[j-v[i]]<inf)f[j]=min(f[j],f[j-v[i]]+w[i]);
}
_for(i,1,1e5)if(f[i]-1<=m)ans=i;
printf("%lld\n",ans);
又是个板子。
转移方程：
const ll N=3010,inf=1ll<<40;
ll n,m,f[N][N],jl[N][N],li[N][N],lj[N][N],ans,w;
char s[N],t[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
void print(ll i,ll j){
if(li[i][j]&&lj[i][j])print(li[i][j],lj[i][j]);
if(jl[i][j])putchar(s[i]);
}
inline void In(){
scanf("%s",s+1),n=strlen(s+1);
scanf("%s",t+1),m=strlen(t+1);
_for(i,1,n){
_for(j,1,m){
if(f[i-1][j]<f[i][j-1])f[i][j]=f[i][j-1],li[i][j]=i,lj[i][j]=j-1,jl[i][j]=0;
else f[i][j]=f[i-1][j],li[i][j]=i-1,lj[i][j]=j,jl[i][j]=0;
if(s[i]==t[j]&&f[i][j]<=f[i-1][j-1]+1)f[i][j]=f[i-1][j-1]+1,li[i][j]=i-1,lj[i][j]=j-1,jl[i][j]=1;
}
}
_for(i,1,n)if(ans<f[i][m])ans=f[i][m],w=i;
print(w,m),puts("");
return;
}
}
经典拓扑题。
设 \(dis_u\) 是到 \(u\) 的最长路，则显然有转移方程：
可以发现最后一个到点 \(u\) 的点 \(v\) 一定是层数最深的，也是 \(\max_{(v,u)\in\mathbb{E}}\{dis_v\}\)。
那么我们每次到点 \(u\) 都将其入度减一，如果有一个点把它的入度减成了 \(0\)，那么这个点就是我们要求的点 \(v\)。
时间复杂度 \(\Theta(n+m)\)。
const ll N=1e5+10,inf=1ll<<40;
ll n,m,dis[N],in[N],ans;vector<ll>tu[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void GetDis(){
queue<pair<ll,ll> >q;
_for(i,1,n)if(!in[i])q.push(make_pair(i,0));
while(!q.empty()){
ll u=q.front().first;
dis[u]=q.front().second,q.pop();
far(v,tu[u]){
--in[v];
if(!in[v])q.push(make_pair(v,dis[u]+1));
}
}
return;
}
inline void In(){
n=rnt(),m=rnt();
_for(i,1,m){
ll x=rnt(),y=rnt();
++in[y],tu[x].push_back(y);
}
GetDis();
_for(i,1,n)ans=max(ans,dis[i]);
printf("%lld\n",ans);
return;
}
}
const ll N=1010,P=1e9+7,inf=1ll<<40;
ll n,m,f[N][N];char a[N][N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline ll rch(){
char c=getchar();
while(c!='.'&&c!='#')c=getchar();
return c;
}
inline void In(){
n=rnt(),m=rnt();
_for(i,1,n){
_for(j,1,m){
a[i][j]=rch();
if(a[i][j]!='#'){
if(i==1&&j==1){f[i][j]=1;continue;}
if(a[i-1][j]=='.')f[i][j]=(f[i][j]+f[i-1][j])%P;
if(a[i][j-1]=='.')f[i][j]=(f[i][j]+f[i][j-1])%P;
}
}
}
printf("%lld\n",f[n][m]);
return;
}
}
期望 DP。
设 \(f_{i,j}\) 表示前 \(i\) 个硬币里正面朝上的硬币有 \(j\) 个的概率，则转移方程为：
最终答案为：
const ll N=3010,inf=1ll<<40;
ll n;ldb a[N],f[N][N],ans;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline ll rch(){
char c=getchar();
while(c!='.'&&c!='#')c=getchar();
return c;
}
inline void In(){
n=rnt();
f[0][0]=1.0;
_for(i,1,n){
scanf("%Lf",&a[i]);
_for(j,0,i){
f[i][j]=f[i-1][j]*(1-a[i]);
if(j)f[i][j]+=f[i-1][j-1]*a[i];
}
}
_for(i,((n-1)>>1)+1,n)ans+=f[n][i];
printf("%.12Lf\n",ans);
return;
}
}
设 \(f_{i,j,k}\) 表示当前有 \(i\) 盘剩 \(1\) 个，有 \(j\) 盘剩 \(2\) 个，有 \(k\) 盘剩 \(3\) 个。
剩一个的盘子吃完就吃完了，剩两个的盘子吃完会多一个剩一个的盘子，剩三个的盘子吃完会多一个剩两个的盘子。所以 \(f_{i,j,k}\) 应从 \(f_{i-1,j,k},f_{i+1,j-1,k},f_{i,j+1,k-1}\) 转移过来。
直接算一下每种盘子被选中的概率即可，转移方程：
时间复杂度 \(\Theta(n^3)\)。
n=rnt();
_for(i,1,n){
a[i]=rnt();
if(a[i]==1)++c1;
if(a[i]==2)++c2;
if(a[i]==3)++c3;
}
_for(k,0,n){
_for(j,0,n){
_for(i,0,n){
if(i)f[i][j][k]+=f[i-1][j][k]*(ldb(i)/ldb(i+j+k));
if(j)f[i][j][k]+=f[i+1][j-1][k]*(ldb(j)/ldb(i+j+k));
if(k)f[i][j][k]+=f[i][j+1][k-1]*(ldb(k)/ldb(i+j+k));
if(i||j||k)f[i][j][k]+=(ldb(n)/ldb(i+j+k));
}
}
}
printf("%.10Lf\n",f[c1][c2][c3]);
设 \(f_i\) 表示剩余 \(i\) 个石子时先手取能不能赢。
可以发现如果 \(f_{i-a_j}=0\) ，那么先手肯定会取 \(a_j\) 个石子改变局势。
所以转移方程为：
n=rnt(),k=rnt();
_for(i,1,n)a[i]=rnt();
_for(i,1,k)_for(j,1,n)if(i>=a[j]&&!f[i-a[j]])f[i]=1;
puts(f[k]?"First":"Second");
区间 DP。
通过当前枚举的区间的长度来判断是先手下还是后手下再转移。
转移方程为：
n=rnt();
_for(i,1,n){
a[i]=rnt();
ll b=(n&1)?1:-1;
f[i][i]=b*a[i];
}
_for(k,1,n-1){
ll b=((n-k)&1);
_for(i,1,n-k){
if(b)f[i][i+k]=max(f[i+1][i+k]+a[i],f[i][i+k-1]+a[i+k]);
if(!b)f[i][i+k]=min(f[i+1][i+k]-a[i],f[i][i+k-1]-a[i+k]);
}
}
printf("%lld\n",f[1][n]);
很典的前缀和优化。
设 \(g_{i,j}\) 表示选 \(j\) 颗糖恰好分给前 \(i\) 个人的方案数，转移方程为：
时间复杂度 \(\Theta(nk^2)\)，需要优化一下。
那么设 \(f_{i,j}\) 表示最多选 \(j\) 颗糖分给前 \(i\) 个人的方案数，转移方程为：
时间复杂度 \(\Theta(nk)\)，初始状态 \(f_{0,i}=1(0\le i\le k)\)，答案为 \((f_{n,k}-f_{n,k-1})\)。
可以用滚动数组滚掉一维。
n=rnt(),k=rnt();
_for(i,0,k)f[i]=1;
_for(i,1,n){
a[i]=rnt();
for_(j,k,1)f[j]=(f[j]-((j<=a[i])?0:f[j-a[i]-1])+P)%P;
_for(j,0,k)f[j]=(f[j-1]+f[j])%P;
}
printf("%lld\n",(f[k]-f[k-1]+P)%P);
弱化版石子合并。
设 \(f_{i,j}\) 表示将 \(i\) 到 \(j\) 的数字合起来的最小代价，显然转移方程为：
n=rnt();
_for(i,1,n)s[i]=s[i-1]+rnt();
_for(k,2,n){
_for(i,1,n-k+1){
f[i][i+k-1]=inf;
_for(j,i+1,i+k-1)f[i][i+k-1]=min(f[i][i+k-1],f[i][j-1]+f[j][i+k-1]);
f[i][i+k-1]+=s[i+k-1]-s[i-1];
}
}
printf("%lld\n",f[1][n]);
数据范围 \(1\le n\le 21\)，显然是状压 DP。
设 \(f_{i,j}\) 表示前 \(i\) 个人的匹配状态为 \(j\)，因为 \(i\) 个人只能匹配上 \(i\) 个人，所以 匹配条件为\(j\) 的二进制下 \(1\) 的个数为 \(i\)，可以省掉第一位。转移方程：
时间复杂度 \(\Theta(n2^n)\)。
const ll N=25,P=1e9+7,inf=1ll<<40;
ll n,U,tu[N],f[1<<21],ans;vector<ll>qk[N];
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline ll CntOne(ll num){ll c=0;while(num)++c,num-=(num&-num);return c;}
inline void Pre(){_for(i,1,U)qk[CntOne(i)].push_back(i);return;}
inline void DP(){
f[0]=1;
_for(i,1,n){
far(j,qk[i]){
ll k=j;
while(k){
if(tu[i]&(k&-k))f[j]=(f[j]+f[j^(k&-k)])%P;
k-=(k&-k);
}
}
}
}
inline void In(){
n=rnt(),U=(1<<n)-1;
_for(i,1,n)_for(j,1,n)tu[i]|=rnt()<<(j-1);
Pre(),DP();
printf("%lld\n",f[U]);
return;
}
}
很典的树形 DP。
设 \(f_{u,0/1}\) 表示节点 \(u\) 颜色为 \(0/1\) 时的方案数（\(0\) 白 \(1\) 黑）。
转移方程：
const ll N=1e5+10,P=1e9+7,inf=1ll<<40;
ll n,f[N][2];vector<ll>tu[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
void Dfs(ll u,ll fa){
f[u][0]=f[u][1]=1;
far(v,tu[u]){
if(v==fa)continue;
Dfs(v,u);
f[u][0]=f[u][0]*(f[v][0]+f[v][1])%P;
f[u][1]=f[u][1]*f[v][0]%P;
}
return;
}
inline void In(){
n=rnt();
_for(i,1,n-1){
ll x=rnt(),y=rnt();
tu[x].push_back(y);
tu[y].push_back(x);
}
Dfs(1,0);
printf("%lld\n",(f[1][0]+f[1][1])%P);
return;
}
}
线段树优化 DP。
设 \(f_{i}\) 表示选第 \(i\) 瓶花时最大权值，转移方程显然为：
那么我们用线段树维护一下小于 \(h_i\) 的最大 \(f_i\) 即可。
const ll N=2e5+10,inf=1ll<<40;
ll n,rt,h[N],a[N],f[N],ans;
class SegmentTree{
public:
ll tot=0;
class TREE{public:ll mx,ls,rs;}tr[N<<2];
#define mx(p) tr[p].mx
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define l_s(p) ls(p),l,mid
#define r_s(p) rs(p),mid+1,r
void Update(ll &p,ll l,ll r,ll x,ll val){
if(x<l||r<x)return;
if(!p)p=++tot;
if(l==r)mx(p)=max(val,mx(p));
else{
bdmd;
Update(l_s(p),x,val);
Update(r_s(p),x,val);
mx(p)=max(mx(ls(p)),mx(rs(p)));
}
return;
}
ll Query(ll &p,ll l,ll r,ll le,ll ri){
if(ri<l||r<le||!p)return 0;
if(le<=l&&r<=ri)return mx(p);
else{
bdmd;
return max(Query(l_s(p),le,ri),Query(r_s(p),le,ri));
}
}
}tr;
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline void In(){
n=rnt();
_for(i,1,n)h[i]=rnt();
_for(i,1,n)a[i]=rnt();
_for(i,1,n){
f[i]=tr.Query(rt,1,n,1,h[i])+a[i];
tr.Update(rt,1,n,h[i],f[i]);
ans=max(ans,f[i]);
}
printf("%lld\n",ans);
return;
}
}
想一下 Floyed 是怎么跑的：
即把两条路拼起来。
本道题也可以用类似的思路。设 \(g_{i,j}\) 表示原邻接矩阵，\(f_{k,i,j}\) 表示长度为 \(k\) 的从 \(i\) 到 \(j\) 的路径有多少条。转移方程：
发现这是个矩阵乘法，于是冲个矩阵快速幂就行了。
时间复杂度 \(\Theta(n^3\log_2k)\)。
const ll N=110,P=1e9+7,inf=1ll<<40;
ll n,k,a[N],ans;
class Matrix{
public:
ll a[N][N];
inline void Clear(){memset(a,0,sizeof(a));return;}
inline void One(){_for(i,1,n)a[i][i]=1;return;}
inline ll* operator[](const ll x){return a[x];}
inline Matrix operator*(Matrix q){
Matrix ans;ans.Clear();
_for(i,1,n)_for(j,1,n)_for(k,1,n)
ans[i][j]=(ans[i][j]+a[i][k]*q[k][j]%P)%P;
return ans;
}
}ma;
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline Matrix ksm(Matrix mat,ll b){
Matrix ans;ans.Clear(),ans.One();
while(b){
if(b&1)ans=ans*mat;
mat=mat*mat,b>>=1;
}
return ans;
}
inline ll GetAnswer(Matrix mat){
ll ans=0;
_for(i,1,n)_for(j,1,n)ans=(ans+mat[i][j])%P;
return ans;
}
inline void In(){
n=rnt(),k=rnt();
_for(i,1,n)_for(j,1,n)ma[i][j]=rnt();
printf("%lld\n",GetAnswer(ksm(ma,k)));
return;
}
}
数位 DP。
设 \(a_i\) 表示上限的第 \(i\) 位（从高位开始数），\(f_{i,j,k}(k\in\{0,1\})\) 表示第 \(i\) 位为 \(j\) 且有（\(k=1\)）无（\(k=0\)）限制的方案数。（限制指前 \(i-1\) 位是否和上限数的前 \(i-1\) 位相同）
然后就非常好转移了，初始状态 \(f_{0,0,1}=1\)，转移方程：
答案为 \(f_{\operatorname{lenth}(n),0,0}+f_{\operatorname{lenth}(n),0,1}-1\)（去掉 \(0\)）。
const ll N=1e4+10,P=1e9+7,inf=1ll<<40;
ll d,len,ans,num,f[N][110][2];char a[N];
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline void In(){
scanf("%s",a+1),d=rnt();
len=strlen(a+1);
f[0][0][1]=1;
_for(i,1,len){
a[i]-='0';
_for(j,0,d-1){
f[i][j][1]=f[i-1][((j-a[i])%d+d)%d][1];
_for(k,0,9)f[i][j][0]=(f[i][j][0]+f[i-1][((j-k)%d+d)%d][0])%P;
_for(k,0,a[i]-1)f[i][j][0]=(f[i][j][0]+f[i-1][((j-k)%d+d)%d][1])%P;
}
}
printf("%lld\n",(f[len][0][0]+f[len][0][1]-1+P)%P);
return;
}
}
设 \(f_{i,j}\) 表示第 \(i\) 个数是前 \(i\) 个数中第 \(j\) 大的方案数。
转移方程：
const ll N=3e3+10,P=1e9+7,inf=1ll<<40;
ll n,f[N],sum[N],ans;char s[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void In(){
n=rnt(),scanf("%s",s+2);
_for(i,1,n){
_for(j,1,n){
if(i==1)f[j]=1;
else if(s[i]=='<')f[j]=sum[j-1];
else f[j]=(sum[i-1]-sum[j-1]+P)%P;
}
_for(j,1,n)sum[j]=(sum[j-1]+f[j])%P;
}
printf("%lld",sum[n]);
return;
}
}
如果你会枚举子集的话应该看一眼就知道怎么做了，但我不会。
看数据范围知状压，首先预处理出 \(val_i\)，表示把状态 \(i\) 中的每个数放在一组的得分，时间复杂度 \(\Theta(2^nn^2)\)。
然后对于每一个状态，把它的一个子集当成一组，剩下的部分从当成上一个部分转移来。即：
这部分需要枚举子集，时间复杂度 \(\Theta(3^n)\)。
const ll N=20,U=1<<17,inf=1ll<<40;
ll n,u,a[N][N],val[U],f[U],ans;
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void Pre(){
_for(i,1,u)_for(j,1,n)if((i>>(j-1))&1)
_for(k,j+1,n)if((i>>(k-1))&1)val[i]+=a[j][k];
return;
}
inline void DP(){
_for(i,1,u)for(int j=i;j;j=(j-1)&i)
f[i]=max(f[i],f[i^j]+val[j]);
return;
}
inline void In(){
n=rnt(),u=(1<<n)-1;
_for(i,1,n)_for(j,1,n)a[i][j]=rnt();
Pre(),DP();
printf("%lld",f[u]);
return;
}
}
咕咕咕。
咕咕咕。
比较平凡的的背包 DP。
有一个限重，那么上限就不能是 \(2\times10^4\) 了，而应该是 \(s_i+w_i\)。
然后发现直接按原顺序跑会有问题，因为有的箱子承重拉不满，会有剩余。这时只要按 \(s_i+w_i\) （即上限）排个序就行了。
不是很理解 橙题+改上限+排序 为什么等于 蓝题。
const ll N=1e7+10,inf=1ll<<40;
ll n,f[N],ans;
class BOX{
public:
ll w,s,v;
inline bool operator<(const BOX &bx)const{
return w+s<bx.w+bx.s;
}
}b[N];
namespace SOLVE{
inline ll rnt(){
ll x=0,w=1;char c=getchar();
while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline void In(){
n=rnt(),f[0]=1;
_for(i,1,n)b[i].w=rnt(),b[i].s=rnt(),b[i].v=rnt();
sort(b+1,b+n+1);
_for(i,1,n)for_(j,b[i].s+b[i].w,b[i].w)
if(f[j-b[i].w])f[j]=max(f[j],f[j-b[i].w]+b[i].v);
_for(i,1,2e4)ans=max(ans,f[i]);
printf("%lld",ans-1);
return;
}
}
容斥 DP。
首先我们知道从 \((x1,y1)\) 走到 \((x2,y2)\) 的方案数为 \(cnt(x1,y1,x2,y2)=\dbinom{\left|x1+y1-x2-y2\right|}{\left|x1-x2\right|}\)。
（从 \((x1,y1)\) 走到 \((x2,y2)\) 必然需要 \(\left|x1+y1-x2-y2\right|\) 步，在其中选出 \(\left|x1-x2\right|\) 步作为向下走）
然后我们考虑一下从 \((1,1)\) 走到一个不能经过的点 \((x_i,y_i)\) 有多少种方案。答案显然不是 \(cnt(1,1,x_i,y_i)\)，因为路上会有不能经过的点。
那么进行一下容斥：用总方案数减去经过不能经过的点的方案数。
那么设 \(f_i\) 表示从 \((1,1)\) 走到一个不能经过的点 \((x_i,y_i)\) 有多少种方案，则：
答案显然就是：
时间复杂度 \(O(n^2)\)。
namespace SOLVE {
typedef long double ldb;
typedef long long ll;
typedef double db;
const ll N = 1e6 + 10, M = 1e6, P = 1e9 + 7;
ll h, w, n, fac[N], inv[N], f[N], ans;
class hinder {
public:
ll x, y;
inline bool operator < (const hinder another) const {
return (x == another.x) ? (y < another.y) : (x < another.x);
}
} hd[N];
inline ll rnt () {
ll x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
inline ll FastPow (ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % P;
a = a * a % P, b >>= 1;
}
return ans;
}
inline void Pre () {
fac[0] = 1;
_for (i, 1, M) fac[i] = fac[i - 1] * i % P;
inv[M] = FastPow (fac[M], P - 2);
for_ (i, M - 1, 0) inv[i] = inv[i + 1] * (i + 1) % P;
return;
}
inline ll C (ll n, ll m) {
if (!m) return 1;
if (n < m) return 0;
return fac[n] * inv[n - m] % P * inv[m] % P;
}
inline ll GetCnt (ll i, ll j) {
return C (hd[i].x - hd[j].x + hd[i].y - hd[j].y, hd[i].x - hd[j].x);
}
inline void In () {
h = rnt (), w = rnt (), n = rnt ();
_for (i, 1, n) hd[i].x = rnt (), hd[i].y = rnt ();
std::sort (hd + 1, hd + n + 1);
hd[0].x = hd[0].y = 1, hd[n + 1].x = h, hd[n + 1].y = w;
return;
}
inline void Solve () {
_for (i, 1, n) {
f[i] = GetCnt (i, 0);
_for (j, 1, i - 1) {
if (hd[j].y > hd[i].y) continue;
f[i] = (f[i] - GetCnt (i, j) * f[j] % P + P) % P;
}
}
ans = GetCnt (n + 1, 0);
_for (j, 1, n) ans = (ans - GetCnt (n + 1, j) * f[j] % P + P) % P;
return;
}
inline void Out () {
printf ("%lld\n", ans);
return;
}
}
正序开不动了，那就尝试一下倒序开题破局！
斜率优化 DP 板子。
随便推一推可得到式子：
令：
然后直接套个斜率优化结束。
const ll N=2e5+10,inf=1ll<<40;
ll n,c,h[N],f[N],ans;
ll q[N],hd=1,tl=1;
namespace SOLVE{
char buf[1<<20],*p1,*p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline ll rnt(){
ll x=0,w=1;char c=gc();
while(!isdigit(c)){if(c=='-')w=-1;c=gc();}
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=gc();
return x*w;
}
inline ll k(ll i){return 2*h[i];}
inline ll b(ll i){return f[i]-h[i]*h[i]-c;}
inline ll x(ll i){return h[i];}
inline ll y(ll i){return h[i]*h[i]+f[i];}
inline void DP(){
q[1]=1;
_for(i,2,n){
while(hd<tl&&(y(q[hd+1])-y(q[hd]))<=k(i)*(x(q[hd+1])-x(q[hd])))++hd;
f[i]=y(q[hd])-k(i)*x(q[hd])-b(i);
while(hd<tl&&(x(q[tl])-x(q[tl-1]))*(y(i)-y(q[tl]))<=(x(i)-x(q[tl]))*(y(q[tl])-y(q[tl-1])))--tl;
q[++tl]=i;
}
return;
}
inline void In(){
n=rnt(),c=rnt();
_for(i,1,n)h[i]=rnt();
DP();
printf("%lld\n",f[n]);
return;
}
}
我正在使用SublimeText2，同时遵循MichaelHartl的RubyonRails教程。可以在http://ruby.railstutorial.org/book/ruby-on-rails-tutorial找到我所指的教程的具体部分。(ctrl+F“list5.26”)。我能够创建规范/支持文件。但是，在尝试创建spec/support/utilities.rb文件时，我收到消息“无法保存~/rails_projects/sample_app/spec/support/utilities.rb”。有人知道为什么会这样吗？SublimeText论坛上有人似乎遇到了完全相同的问
整理|王启隆透过「历史上的今天」，从过去看未来，从现在亦可以改变未来。今天是2023年4月26日，在2017年的今天，中国首艘国产001A型航空母舰在大连完成了下水，从开工到下水，历时3年多时间。回首过去，眺望未来，在科技历史上的每个4月26日里，还发生过哪些影响深远的关键事件呢？1938年4月26日：编程校验领域图灵奖得主ManuelBlum出生曼纽尔·布卢姆（ManuelBlum）出生于1938年4月26日，他是委内瑞拉的计算机科学家、卡内基梅隆大学的教授，因对计算复杂度理论做出的贡献，以及在密码学和编程校验上的应用而获1995年图灵奖。布卢姆出生于委内瑞拉的一个犹太家庭，他曾在麻省理工学
我想安装gitlab，不推荐使用任何ruby版本管理器。但是这是我的操作系统Linuxdqa-dev3.13.0-24-generic#46-UbuntuSMPThuApr1019:08:14UTC2014i686i686i686GNU/Linuxlinkingshared-objectpsych.soinstallingdefaultpsychlibrariesmake[2]:Leavingdirectory`/home/poc/ruby-2.0.0-p451/ext/psych'make[2]:Enteringdirectory`/home/poc/ruby-2.0.0-p451/
我觉得我快要疯了，但是alert()和console.log()拒绝在上任何地方工作火狐26。起初我以为这是我自己网站的问题，但我终究无法通过javascript:urls、Firebug使其正常工作，我什至在jsfiddle.net中尝试过通过将alert('test');放在脚本面板中。尝试卸载并重新安装，没有成功。我运行的唯一扩展是Firebug。哎呀，当我在写这篇文章时不小心点击了后退按钮时，Stackoverflow甚至没有提示我离开。还有，我确保在alert()和console.log()中有一些内容我所说的不工作是指Firefox将代码视为不存在，没有任何反应。再一次，这
1.coo存储方式采用三元组(row,col,data)(或称为ijvformat)的形式来存储矩阵中非零元素的信息。coo_matrix的优点：有利于稀疏格式之间的快速转换（tobsr()、tocsr()、to_csc()、to_dia()、to_dok()、to_lil()；允许重复项（格式转换的时候自动相加）；能与CSR/CSC格式的快速转换coo_matrix的缺点：不能直接进行算术运算，包括赋值初始化方式：coo_matrix(D),D代表密集矩阵赋值：>>>importnumpyasnp>>>fromscipy.sparseimportcoo_matrix>>>_row=np.ar
如果我有35个字符需要分配标记，我将需要使用小写和大写。如果我已经使用了所有小写ASCII字符，我该如何处理大写ASCII字符？我已经得到26的小写字母，但是当我添加三个大写ASCII时，它输出A|B|C|...让我解释一下。代码如下:@ECHOOFFSETLOCALSET"sourcedir=C:\Users\aborgetti\Desktop\PipeDelimiterProject"SET"destdir=C:\Users\aborgetti\Desktop\PipeDelimiterProject"(FOR/f"tokens=1-29delims=|"%%aIN('TYPE"%
我以文本模式在文件中写了一个流。#pythoncodef=open("somewhereinmycomputer","w")f.write("Hello\nWorld")f.write(chr(26))#writingasciicharacter#26tofilef.write("hhh")f.close()我无法读取ASCII字符#26之后的字节。我知道我应该用二进制模式打开文件。是ascii字符#26EOF字符。如您所知，没有这样的东西，即没有EOF字符。那么什么是问题呢？这是操作系统相关的问题吗？(我在MicrosoftWindows中尝试过)。 最佳
前言我是去年9月22日才正式学习网络安全的，之前在国营单位工作了4年，在长沙一个月工资只有5000块，而且看不到任何晋升的希望，如果想要往上走，那背后就一定要有关系才行。而且国营单位的气氛是你干的多了，领导觉得你有野心，你干的不多，领导却觉得你这个人不错。我才26周岁，实在的受不了这种工作氛围，情绪已经压制了很多久，一心想着要跳出来，却一直找不到合适的机会。因为身边的朋友有在长沙做安全研发的，他工作了四五年的时间，可以在北京拿到3万的月薪，说心里话我是真的羡慕，这远超出了我的认知范围。所以经过朋友的推荐，我开始学习网络安全，一共学了大概5个多月的时间，今年的3月6号在长沙找到了一份安全研发的工
我已将我的应用程序迁移到babel7beta，除了测试之外，一切似乎都正常。我想我已经阅读了所有内容，但我仍然收到此错误:●TestsuitefailedtorunRequiresBabel"^7.0.0-0",butwasloadedwith"6.26.0".Ifyouaresureyouhaveacompatibleversionof@babel/core,itislikelythatsomethinginyourbuildprocessisloadingthewrongversion.Inspectthestacktraceofthiserrortolookforthefirst
我正在为可映射的电子表格导出功能创建一些客户端函数。我正在使用jQuery来管理列的排序顺序，但每一列的排序方式都像Excel电子表格，即abcde......xyzaaabacad等等如何将数字生成为字母？我应该定义一个固定的值数组吗？还是有一种动态的方式来生成它？ 最佳答案 我想你正在寻找这样的东西functioncolName(n){varordA='a'.charCodeAt(0);varordZ='z'.charCodeAt(0);varlen=ordZ-ordA+1;vars="";while(n>=0){s=Strin