首页 > 其他分享 >DP全家桶（长期）

DP全家桶（长期）

时间：2024-07-27 23:18:08浏览次数：15  
标签：长期 ch int nb 全家 dp DP nw

DP

序言

动态规划（DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

运用DP必须满足两个条件：

  • 最优子结构：即当前子状态是最优的，不会出现更优情况。
  • 无后效性：即当前状态的改变不会对后续状态产生影响。

其实第一个性质是大部分题目都满足的，而无后效性可能就需要选手们自己分析要求，改变思路来使其无后效性（其实这种题也不多）

一般来说，DP解题顺序为：

  1. 分析题目主要性质
  2. 根据性质特点列出DP状态
  3. 分析DP转移方程
  4. 解剖细节
  5. 敲代码

其实最主要的就是列出DP状态与转移方程，这也是DP为什么会成为大部分初学者的噩梦的原因，因为通常DP题的题面会给人很强的误导性，可能会让大家想到搜索、退火等算法。

但从个人角度来说，DP最主要的就是思维的敏捷性，比拼的是能否快速地分析题干要求，去除不必要的性质。

本文将会从各大DP中总结规律以及举例题来帮助理解这一算法。

ex：本文是一篇个人记述学习总结的文章，且更偏向省选级别选手的难度，但还是只会从基本开始，不过思路可能会非常简洁（时间不够）

线性DP

最最最基本的DP，这种一般会有很强的子结构特性。一般来说都是能很轻易地分析的。这里就放一道例题的优化吧

B3637 最长上升子序列

典中典的题，相信也是所有DP初学者的必做题目。

考虑定义 \(f_{i}\) 表示前 \(i\) 个元素构成的最长上升子序列的长度。

显然能发现 \(f_i\) 中必定单调不减，这使我们联想到了单调栈。考虑当前元素 \(a_i\) 在 \(f\) 中的位置，可以使用二分或者树状数组实现。然后判断当前位置的序号与当前最长上升子序列长度的大小，若大，意味着当前元素必定可以使最长上升子序列长度增加，故答案加一即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int n;
int a[5020];
int dp[5020];
signed main(){
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    dp[1]=a[1];
    int ans=1;
    for(int i=2;i<=n;++i){
        int l=1,r=ans,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(a[i]<=dp[mid]) r=mid-1;
            else l=mid+1;
        }
        dp[l]=a[i];
        if(l>ans) ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

由于线性DP过于板，这里不再详述。

区间DP

其实也算是线性DP的一种，不过还是单独拿出来吧。

通常解题思路是考虑某一段区间的DP状态，枚举区间断点进行两边的合并更新答案。

P1880 [NOI1995] 石子合并

还是板子题，设 \(f_{i,j}\) 表示 \(i\) 到 \(j\) 之间的答案，那么只需要枚举一个 \(k，i\le k < j\)，然后就有 \(f_{i,j}=f_{i,k}+f_{k+1,j}\)，这道题只需要维护两个即可。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[300];
int dpma[300][300];
int dpmi[300][300];
int s[300];
inline int d(int i,int j){
	return s[j]-s[i-1];
}
int main()
{
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		a[i+n]=a[i];
	}
	for(int i=1;i<=2*n;++i){
		dpma[i][i]=dpmi[i][i]=0;
		s[i]=s[i-1]+a[i];
	}
	for(int len=1;len<=n;++len){
		for(int i=1,j=i+len;(j<2*n) && (i<=2*n);++i,j=i+len){
			dpmi[i][j]=0x3f3f3f3f;
			for(int k=i;k<j;++k)
			{
				dpma[i][j]=max(dpma[i][j],dpma[i][k]+dpma[k+1][j]+d(i,j));
				dpmi[i][j]=min(dpmi[i][j],dpmi[i][k]+dpmi[k+1][j]+d(i,j));
			}
		}
	}
	int minl=0x3f3f3f3f;
	int maxx=-1;
	for(int i=1;i<=n;++i)
	{
		maxx=max(maxx,dpma[i][i+n-1]);
		minl=min(minl,dpmi[i][i+n-1]);
	}
	cout<<minl<<endl<<maxx;
	return 0;
}

背包DP

其实这个我都觉得没有太大必要，网上已经很详尽了，这里给一点思路即可。

0-1 背包：

设 \(f_{i,j}\) 表示前 \(i\) 个选了重量为 \(j\) 的物品的价值。那么当前物品可选可不选，不选时答案不变，即 \(f_{i,j}=f_{i-1,j}\)。
要选时答案即为前一个物品没算当前物品重量的价值加上当前价值，即 \(f_{i,j}=f_{i-1,j-w_i}+v_i\)，二者合起来求最大就ok了

完全背包：

其实就是将 0-1 背包代码中倒着枚举的 \(j\) 正着枚举就ok了，读者们可以想一想为什么。

多重背包：

多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有 \(k_i\) 个，而非一个。

朴素的想法是每一个物品都处理一次。

也可以二进制分组。

混合背包：

前三种组合在一起。

有的只能取一次，有的能取无限次，有的只能取 \(k\) 次。

分讨一下，或者全用二进制分组。

二维费用背包：

选一个物品会消耗两种重量（如经费，时间）。

不就是再开一维嘛

分组背包：

每组中的物品只能选一个。

每组内做一次01。见代码。

#include<bits/stdc++.h>
using namespace std;
int v,n,t;
int x;
int g[205][205];
int i,j,k;
int w[10001],z[10001];
int b[10001];
int dp[10001];
int main(){
    cin>>v>>n;
    for(i=1;i<=n;i++){
        cin>>w[i]>>z[i]>>x;
        t=max(t,x);
        b[x]++;
        g[x][b[x]]=i;
    }
    for(i=1;i<=t;i++){
        for(j=v;j>=0;j--){
            for(k=1;k<=b[i];k++){
                if(j>=w[g[i][k]]){
                    dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);
                }
            }
        }
    }
    cout<<dp[v];
    return 0;
}

状压DP

将一种状态压缩为一个数进行DP。通常来说数据规模极小，不超过 \(20\)。

P1896 [SCOI2005] 互不侵犯

也是板子，用二进制表示上一行国王在哪儿，枚举下一行状态转移。

#include<bits/stdc++.h>
#define int long long
template<typename P>
inline void read(P &x){
   	P res=0,f=1;
   	char ch=getchar();
   	while(ch<'0' || ch>'9'){
   		if(ch=='-') f=-1;
   		ch=getchar();
   	}
   	while(ch>='0' && ch<='9'){
   		res=res*10+ch-'0';
   		ch=getchar();
	}
	x=res*f;
}
using namespace std;
int T=1;
int n,K;
int bitcount(unsigned int n){
    int count=0;
    while(n){
        count++;
        n&=(n-1);
    }
    return count;
}
int dp[10][82][(1<<10)];
bool pd[(1<<9)+5],pd2[(1<<9)+5][(1<<9)+5];
void Init(){
	for(int i=0;i<(1<<9);++i){
		int p=i,las=-1;
		bool flag=1;
		while(p>0){
			int now=p%2;
			p/=2;
			if(now==las && now==1){
				pd[i]=0;
				flag=0;
				break;
			}
			else las=now;
		}
		pd[i]=flag;
		if(pd[i]){
			for(int j=0;j<(1<<9);++j){
				bool o=1;
				for(int w=0,ww=1;w<9;ww<<=1,++w){
					bool i1=i&ww;
					bool j1=j&ww;
					bool i2=i&(ww<<1);
					bool j2=j&(ww<<1);
					if(i1+i2+j1+j2>1){
						o=0;
						break;
					}
				}
				pd2[i][j]=o;
			}
		}
	}
}
signed main(){
	read(n),read(K);
	Init();
	for(int i=0;i<(1<<n);++i) dp[1][bitcount(i)][i]=1;
	for(int i=2;i<=n;++i){
		for(int k=0;k<=K;++k){
			for(int S=0;S<(1<<n);++S){
				if(pd[S] && bitcount(S)<=k)
				for(int Z=0;Z<(1<<n);++Z){
					if(pd2[S][Z])dp[i][k][S]+=dp[i-1][k-bitcount(S)][Z];
				}
			}
		} 
	}
	int ans=0;
	for(int S=0;S<(1<<n);++S) ans+=dp[n][K][S];
	cout<<ans<<endl;
	return 0;
}

P2704 [NOI2001] 炮兵阵地

一个炮兵会影响两行，压两行就行。

ex：插头DP，后面讲

树形DP

就是把DP的操作搞到树上。基本思路无异。

P1352 没有上司的舞会

要么父亲来儿子必定不来，要么父亲不来儿子可来可不来。3种情况。

#include<bits/stdc++.h>
using namespace std;
#define MAXN 6005
int h[MAXN];
int v[MAXN];
vector<int> son[MAXN];
int f[MAXN][2];
void dp(int x){
    f[x][0]=0;
    f[x][1]=h[x];
    for(int i=0;i<son[x].size();i++){
        int y=son[x][i];
        dp(y);
        f[x][0]+=max(f[y][0],f[y][1]);
        f[x][1]+=f[y][0];
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        son[y].push_back(x);
        v[x]=1;
    }
    int root;
    for(int i=1;i<=n;i++)if(!v[i]) {root=i;break;}
    dp(root);
    cout<<max(f[root][0],f[root][1])<<endl;
    return 0;
}

P2014 [CTSC1997] 选课

树上背包板子，先枚举子树内情况进行背包，然后进行背包合并到父亲，向上递归。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;
const int Max=320;
int n,m;
struct edge{
    int to,nxt;
}e[Max<<1];
int head[Max],cnt=0;
void add(int u,int v){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int dp[Max][Max];
void work(int u){
    for(int i=head[u];i;i=e[i].nxt) work(e[i].to);
    for(int i=head[u];i;i=e[i].nxt){
        int to=e[i].to;
        for(int j=m;j>0;--j){
            for(int k=0;k<j;++k){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[to][k]);
            }
        }
    }
}
signed main(){
    read(n),read(m);
    ++m;
    for(int i=1;i<=n;++i){
        int fa;
        read(fa),read(dp[i][1]);
        add(fa,i);
    }
    work(0);
    cout<<dp[0][m]<<endl;
    return 0;
}

换根DP

树上的DP，每次会将树根 \(root\) 进行改变，其实只需要分析改变根会造成的影响，可能会有分讨。

P3478 [POI2008] STA-Station

其实每次换根使 \(root \rightarrow u\),其实会使答案 \(-size_u+size_1-size_u\)，还是很显然的，代码也很好写。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
const int Max=1e6+10;
int n;
struct edge{
    int to,nxt;
}e[Max<<1];
int head[Max],cnt=0;
void add(int u,int v){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int siz[Max];
int dp[Max];
void dfs1(int u,int fa,int dep){
    siz[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int to=e[i].to;
        if(to==fa) continue;
        dfs1(to,u,dep+1);
        siz[u]+=siz[to];
    }
    dp[1]+=dep;
}
void dfs2(int u,int fa){
    for(int i=head[u];i;i=e[i].nxt){
        int to=e[i].to;
        if(to==fa) continue;
        dp[to]=max(dp[to],dp[u]-siz[to]*2+siz[1]);
        dfs2(to,u);
    }
}
signed main(){
    read(n);
    for(int i=1;i<n;++i){
        int u,v;
        read(u),read(v);
        add(u,v);
        add(v,u);
    }
    dfs1(1,0,0);
    dfs2(1,0);
    int maxx=*max_element(dp+1,dp+n+1);
    for(int i=1;i<=n;++i) if(dp[i]==maxx) {cout<<i<<endl;break;}
    return 0;
}

数位DP

这个是我比较喜欢的DP了，代表性很强，而且很有意思。

一般是讨论 \([l,r]\) 区间内每个数字出现次数、所有数字之和...总之就是跟数字每一位有关。

一般会转换为 \([1,r]-[1,l-1]\)

P2602 [ZJOI2010] 数字计数

就是去DP每个数位能填的数字，分别记录答案。注意要判断是否达上界和前导 \(0\) 即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int a,b;
int f[15][2][15][2];
int num[15];
int dfs(int now,int x,int sum,bool op0,bool lim){
    int res=0;
    if(now==0) return sum;
    if(f[now][lim][sum][op0]!=-1) return f[now][lim][sum][op0];
    for(int i=0;i<=9;++i){
        if(lim && i>num[now]) break;
        res+=dfs(now-1,x,sum+((!op0 || i) && (i==x)),(op0) && (i==0),!((!lim) || (i<num[now])));
    }
    f[now][lim][sum][op0]=res;
    return res;
}
int work(int sum,int x){
    int len=0;
    while(sum){
        num[++len]=sum%10;
        sum/=10;
    }
    memset(f,-1,sizeof(f));
    return dfs(len,x,0,1,1);
}
signed main(){
    read(a),read(b);
    for(int i=0;i<=9;++i){
        cout<<work(b,i)-work(a-1,i)<<' ';
    }
    return 0;
}

P4999 烦人的数学作业

跟上一题几乎一模一样，但这个不需要枚举每一个数字，其他地方稍微改改就行。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
int T=1;
int f[200][200];
int num[1000010];
int a,b;
const int mod=1e9+7;
int dfs(int now,int sum,bool lim){
    if(now==0) return sum;
    int res=0;
    if(f[now][sum]>=0 && !lim) return f[now][sum]%mod;
    int upp=lim?num[now]:9;
    for(int i=0;i<=upp;++i){
        res+=dfs(now-1,sum+i,lim && i==num[now]);
        res%=mod;
    }
    if(!lim) f[now][sum]=res%mod;
    return res%mod;
}
int work(int sum){
    int len=0;
    while(sum){
        num[++len]=sum%10;
        sum/=10;
    }
    memset(f,-1,sizeof(f));
    return dfs(len,0,1)%mod;
}
signed main(){
    auto solve=[&](){
        read(a),read(b);
        int ans=0;
        ans+=work(b)-work(a-1)+mod;
        ans%=mod;
        cout<<ans<<endl;
    };
    read(T);
    while(T--) solve();
    return 0;
}

计数DP

顾名思义，就是统计方案数的DP，DP的过程没有本质区别。，其实市面上很多求方案数的题都跟这个挂钩，读者们可以注意一下。

P2327 [SCOI2005] 扫雷

典典典，这道题其实只需要根据第一个格子的数字再往后判断是否合法即可，不难，所以我们改一下题目：

有一些格子不知道是多少。

这样呢，就发现前面的会影响后面的。

但其实只会影响周围俩，所以还是可以做的。

其实只需要设 \(f_{i,0/1,0/1}\) 表示前 \(i\) 个位置，第 \(i\) 个位置有没有雷，第 \(i-1\) 个格子有没有雷。对应状态转移即可。没写代码。

P2051 [AHOI2009] 中国象棋

令 \(f_{i,j,k}\) 为考虑到第 \(i\) 行，有 \(j\) 列填了1个棋子，\(k\) 列填了2个棋子的方案数。

然后枚举行，处理每一列的情况。有6种，一个都不放有一种，放一个有两种放的位置（一个上面已经放了一个，一个上面还是空的），放两个有三种放的位置，都放上面空的、一个空一个有一个的、两个都放头上有一个的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename P>
inline void read(P &x){
    P res=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        res=res*10+ch-'0';
        ch=getchar();
    }
    x=res*f;
}
const int mod=9999973;
int dp[120][120][120];
int n,m;
int bal(int x){
    return (x*(x-1)/2)%mod;
}
signed main(){
    read(n),read(m);
    int ans=0;
    dp[0][0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j){
            for(int k=0;k<=m-j;++k){
                dp[i][j][k]=dp[i-1][j][k];
                if(k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+1][k-1]*(j+1))%mod;
                if(j>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k]*(m-j+1-k))%mod;
                if(k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1]*j*(m-j-k+1))%mod;
                if(j>=2) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-2][k]*bal(m-j+2-k));
                if(k>=2) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j+2][k-2]*bal(j+2));
                dp[i][j][k]%=mod;
            }
        }
    }
    for(int i=0;i<=m;++i) for(int j=0;j<=m;++j) ans+=dp[n][i][j],ans%=mod;
    cout<<ans<<endl;
    return 0;
}

CF559C Gerald and Giant Chess

接考虑不能走黑色，数据范围太大不好做。

考虑容斥一下，不走黑色的方案数=总的方案数-经过黑点的方案数

不考虑限制从点 \(i\) 走到点 \(j\) 的方案数为：\(C_{x_i+y_i-x_j-y_j}^{x_i-x_j}\)

先把黑点按照坐标排序。

定义 \(f_i\) 表示不经过黑点走到第 \(i\) 个点的方案数。

那么：\(f[i]=C_{x_i+y_i-2}^{x_i-1}-\sum_{j=1}^{i-1}f[j]*C_{x_i+y_i-x_j-y_j}^{x_i-x_j}\)

表示随便走到第 \(i\) 个点的方案数减去经过前面一个黑点后剩下随便走的方案数。

令 \((h,w)\) 为第 \(n+1\) 个黑点，最终答案就是 \(f_{n+1}\)。

代码还没改对，之后上传。

期望DP

倒数第二不会的来了。

实际就是DP套个期望/概率。

  • 期望的一些性质

$ E(X+Y)=E(X)+E(Y)$

\(E(XY)=E(X)E(Y)（X，Y相互独立）\)

\(E(aX+b)=aE(X)+b\)

\(E(c)=c\)

CF148D Bag of mice

设 \(f(i,j)\) 表示有 \(i\) 只白鼠，\(j\) 只黑鼠时A先手胜的概率

初始状态

全白时，显然先手必胜

有一只黑鼠时，先手若抽到黑鼠则后手必胜，所以先手首回合必须抽到白鼠

\(f(i,0)=1,f(i,1)=\frac{i}{i+1}\)

转移方程 \(f(i,j)\)

先手抽到白鼠，胜：\(\frac{i}{i+j}\)

先手抽到黑鼠，后手抽到白鼠，败： \(0\)

先手抽到黑鼠，后手抽到黑鼠，跑一只白鼠：\(\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{i}{i+j-2}\times f(i-1,j-2)\)

先手抽到黑鼠，后手抽到黑鼠，跑一只黑鼠：\(\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}\times f(i,j-3)\)

\(f(i,j)=\frac{i}{i+j}+\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{i}{i+j-2}\times f(i-1,j-2)+\frac{j}{i+j}\times \frac{j-1}{i+j-1}\times \frac{j-2}{i+j-2}\times f(i,j-3)\)

\(O(wb)\)

#include<bits/stdc++.h>
using namespace std;
double f[1010][1010];
int w,b;
double dfs(int nw,int nb){
	if(nw==0) return 0.0;
	if(nb==0) return 1.0;
	if(f[nw][nb]>0) return f[nw][nb];
	double ans=0;
	ans+=1.0*nw/(nw+nb);
	if(nb==2)
	ans+=1.0*nb/(nw+nb)*(nb-1)/(nw+nb-1)*dfs(nw-1,nb-2);
	else if(nb>=3)
	ans+=1.0*nb/(nw+nb)*(nb-1)/(nw+nb-1)*(1.0*nw/(nw+nb-2)*dfs(nw-1,nb-2)+1.0*(nb-2)/(nw+nb-2)*dfs(nw,nb-3));
	return f[nw][nb]=ans;
}
signed main(){
	cin>>w>>b;
	printf("%.9lf",dfs(w,b));
	return 0;
}

插头DP

最不会的。

还没懂，懂了补上。

标签：长期,ch,int,nb,全家,dp,DP,nw
From： https://www.cnblogs.com/lizihan00787/p/18327647

相关文章

  • dpdk下ipsec内联卸载（inline offload）测试
    使用intel82599网卡完成。介绍本文介绍了数据平面开发套件(DPDK)框架中的内联IPsec加速支持实现，特别关注英特尔®8259910千兆以太网控制器系列的功能和支持。内联IPsec可用于实现IPsec感知系统，该系统具有比旁路辅助和加速硬件更好的延迟，前提是支持的算法合适。......
  • 7.26 Dp 主题赛 赛后总结
    T1T1看上去就很板，开场后有几个人一直在说话导致我心烦意乱，加上Sorato和Psm很快就切掉，可我确一直没有思路，所以开始的时候很慌。后来冷静下来仔细思考一下，首先注意到数据范围允许\(O(n^2)\)的dp，不难想到设置一个这样的dp状态，\(f[i]\)表示将区间\([1,i]\)变成美丽的所需的最小花......
  • dp专题
    1.花店橱窗原题链接：https://ac.nowcoder.com/acm/contest/87275/1005注意放与不放是平行的查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intva[110][110];intf[1000000];structnode{inta[110];intt;}way[110][110];//......
  • Diffusion|DDPM 理解、数学、代码
    Diffusion论文：DenoisingDiffusionProbabilisticModels参考博客openinnewwindow；参考paddle版本代码：aistudio实践链接openinnewwindow该文章主要对DDPM论文中的公式进行小白推导，并根据ppdiffuser进行DDPM探索。读者能够对论文中的大部分公式如何得来，用在了什么......
  • ScheduledThreadPoolExecutor
    定时任务ScheduledThreadPoolExecutor类有两个用途：指定时间延迟后执行任务；周期性重复执行任务。JDK1.5之前，主要使用Timer类来完成定时任务，但是Timer有以下缺陷：Timer是单线程模式；如果在执行任务期间某个TimerTask耗时较久，就会影响其它任务的调度；Timer的任务调度是基于......
  • 2024736DP专项练习赛
    前言比赛链接榜上那个冒着蓝光的就是我……提交记录跟答辩一样……\(\color{#F8BBD0}Heldivis%%%%%%%%%%%%%%%%%%%\)吐槽一下，虽然挂着DP专题赛的名字，但除了T1T3以外，全是记搜题（虽然好像只有四道题来着）。T1签到题，\(n\)范围很小，先用区间dp求出任意区间达到最终状态......
  • Luogu P3177 树上染色 [ 蓝 ] [ 树形 dp ] [ 贡献思维 ]
    一道很好的树形dp！！！！！树上染色。错误思路定义\(dp[u][i]\)表示以\(u\)为根的子树中，把\(i\)个点染成黑色的最大收益。但这样写，就在转移的时候必须枚举每一个点，复杂度过大，而且还不好写，是十分错误的写法。正确思路一般看到有关树上“路径”的题，就要把路径拆成一个个独立的......
  • DP选讲做题记录 by 付乙淼
    DP选讲P5074EattheTrees最简单的插头DP，轮廓线和插头可以很轻松存储状态和转移。P4719【模板】"动态DP"&动态树分治P5024[NOIP2018提高组]保卫王国动态DP一般就是简单的DP带单点修改，而且给你放到树上，这样你就不得不写树剖，写树剖就需要维护重链，我们就要写出也就是......
  • 【Azure APIM】调用APIM的备份接口时候遇见InvalidParameters错误
    问题描述根据官方文档，可以调用RESTAPI来对APIM执行备份操作。要备份API管理服务，请发出以下HTTP请求：POSThttps://management.chinacloudapi.cn/subscriptions/{subscriptionId}/resourceGroups/{resourceGroupName}/providers/Microsoft.ApiManagement/service/{serviceN......
  • Android开发 - 存储辅助类 SharedPreferences 解析
    SharedPreferences简介SharedPreferences是Android平台上一个轻量级的存储辅助类，用来保存应用的一些常用配置。SharedPreferences的数据以键值对(key,val)的进行保存在以xml形式的文件中。在应用中通常做一些简单数据的持久化缓存从editor的put方法可以看出SharedPreferenc......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99