初探dp优化

起因是在 Huawei的 online camp 上遇到一道题，虽然现在也不知道怎么解决的。当时想法就是是不是四边形不等式或者斜率优化之类的。好像一直以来都知道自己在这方面只是了解，没有很深入♂掌握，趁这次补一下吧qwq。

说到 Dynamic Programming 我就很喜欢大一时候的一句话：But life ,can't satisfy with all factors of Dynamic Programming

dp 也有很多形式的优化，比如是否具有决策单调性，斜率优化，数据结构优化，带权二分，单调栈单调队列优化等等。

前缀和优化

P2513 [HAOI2009]逆序对数列

Description

求长度为 $n$ 的有 $k$ 对逆序对的排列数量 $n,k\le 1000$

Solution

考虑 $dp[i][j]$ 表示 $i$ 的全排列中，逆序数为 $j$ 的数量。

那么有 $dp[i][j] = \sum_{k=max(0,j-i+1)}^{j}dp[i-1][k]$

因为状态转移连续，可以记录前缀和优化。记录$sum=\sum_{k=max(0,j-i+1)}^{j}dp[i][k]$,转移时候注意减去前缀就行。

Code

点击显/隐内容

int n , k, sum;
int dp[1100][1100];
int32_t main()
{
    // dp[i][j] 表示i的全排列中逆序数为j的个数
    cin >> n >> k;
    dp[1][0] = 1;
    for(int i = 2; i <= n; i++){
        sum = 0;
        for(int j = 0; j <= k; j++){
            add(sum, dp[i-1][j]);
            dp[i][j] = sum;
            if(j >= i-1){
                dec(sum,dp[i-1][j-i+1]);
            }
        }
    }
    cout << dp[n][k] << endl;
    return 0;
}

此题加强版 loj6077

洛谷P2511 [HAOI2008]木棍分割

点击显/隐内容

int n , m , a[maxn], sum[maxn], mx, dp[maxn], S[maxn],ans,rem[maxn];
int chk(int x){
	int tot=0,len=0;
	for(int i=1;i<=n;i++){
		if(len+a[i]>x)tot++,len=a[i];
		else len+=a[i];
	}return tot<=m;
}
int DP(int x){
	int k=0;
	for(int i=1;i<=n;i++) for(;k<i;k++) if(sum[i]-sum[k]<=x){rem[i]=k;break;}
	int res=(sum[n]<=x);
	for(int i=1;i<=n;i++){
		if(sum[i]<=x)dp[i]=1;
		S[i]=(S[i-1]+dp[i])%mod;
	}
	for(int i=2;i<=m+1;i++){
		for(int j=1;j<=n;j++){
			dp[j]=S[j-1];
			if(rem[j]-1>=0)dec(dp[j],S[rem[j]-1]);
		}
		for(int j=1;j<=n;j++) S[j]=(S[j-1]+dp[j])%mod;
		add(res,dp[n]);
	}
	return res;
}
int32_t main()
{
	close;
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],sum[i]=sum[i-1]+a[i],umax(mx,a[i]);
	
	int L=mx, R=sum[n],mid;
	while(L<R){
		mid=L+R>>1;
		if(chk(mid))ans=mid, R=mid;
		else L = mid+1;
	}
	cout << ans << " " << DP(ans) << endl; 
	return 0;
}

及时当勉励