首页 > 代码库 > SGU 183 Painting the balls (优化的动态规划)

SGU 183 Painting the balls (优化的动态规划)

2024-07-07 00:42:40   225人阅读

 

题意：给n个白球，选其中一些涂为黑色，且给了涂第i个球的花费为ci，要求每m个连续的球中至少有两个黑球，问最小花费是多少？

 

容易想到一个方程dp[i][j]=min{dp[k][i]}+c[j]

dp[i][j]表示最后上色的两个球分别是第i和第j个球（i<j)时的最优解。

我们从条件每m个连续的球中至少有两个黑球可以得出k的范围j-m<=k<i

如果我们直接按上面这个方程去做的话时间复杂度是O（n*m*m)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define ll long long
#define mod 113
#define INF 100000000
using namespace std;
int c[10005];
int dp[205][105];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) scanf("%d",&c[i]);
    memset(dp,0x7f,sizeof(dp));
    for(int i=2; i<=m; ++i)
        for(int j=1; j<i; ++j)
            dp[i%mod][i-j]=c[i]+c[j];
    for(int i=m+1; i<=n; ++i)
        for(int j=i-m+1; j<i; ++j)
        {
            int minn=INF;
            for(int k=i-m; k<j&&i-k<=m; ++k)
                minn=min(minn,dp[j%mod][j-k]);
            dp[i%mod][i-j]=minn+c[i];
        }
    int ans=INF;
    for(int i=n; i>=n-m+1; --i)
        for(int j=i-1; i-j<=m&&j>=n-m+1; --j)
            ans=min(ans,dp[i%mod][i-j]);

    printf("%d\n",ans);
    return 0;
}
View Code

但如果数据范围再大一点，就不行了。
所以我们需要优化一下转移部分。

对于上面那个方程而言，对于相同i，k的右边界是不变的，左边界随着j的变大的而减小。所以我们可以试着从大到小枚举j，这样k的区间就从小变大了。我们可以利用上一个区间的结果，从而降低转移的时间复杂度。

从另一种角度来阐述:

写一下dp[i][j+1]=min{dp[k][i]}+c[j+1]，这里k的范围是j-m+1<=k<i。

我们发现这里k的范围是和dp[i][j]那个方程里面的k的范围是有重合的，准确说是dp[k][i]是有重合的。我们假设g=min{dp[k][i]},(j-m+1<=k<i)。这样求dp[i][j]=min{dp[k][i]}+c[j]（j-m<=k<i）时，就变成了dp[i][j]=min{dp[j-m][i],g}+c[j]。这样我们只需要以i为阶段，从大到小枚举j就可以把转移这部分的时间复杂度降维O（1）。

这里的计算只适合j大于m的情况，所以需要预处理m以内的部分:dp[i][j]=c[i]+c[j](1<=i<j<=m)。

最终的答案需要从[n-m+1,n]之间的范围之内枚举。

由于卡内存所以要用滚动数组。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#define ll long long
#define mod 101
using namespace std;
int dp[205][205];
int a[10005];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
        scanf("%d",&a[i]);
    for(int i=1; i<=m; ++i)
        for(int j=i+1; j<=m; ++j)
            dp[i][j]=a[i]+a[j];
    for(int i=1; i<=n; ++i)
    {
        int  minn=0x7fffffff;
        for(int j=min(i+m-1,n); j>max(i,m)&&j-i<m; --j)
        {
            minn=min(minn,dp[(j-m+mod)%mod][i%mod]);
            dp[i%mod][j%mod]=minn+a[j];
        }
    }
    int ans=0x7fffffff;
    for(int i=n; i>=n-m+1; --i)
        for(int j=i-1; i-j<m&&j>=n-m+1; --j)
            ans=min(ans,dp[j%mod][i%mod]);
    printf("%d\n",ans);
    return 0;
}
View Code

参考：http://wenku.baidu.com/view/89bd5f1e650e52ea551898fb.html


联系
我们