题解：SP14846 GCJ1C09C - Bribe the Prisoners

· · 题解

SP14846 GCJ1C09C - Bribe the Prisoners

思路分析

本题区间动态规划还是能一眼看出来的，关键在于如何分析释放囚犯的过程。

正着做比较困难，我们考虑反着做：

把每次要释放的囚犯编号看为断点，每次释放囚犯的过程实际上就是将相邻两段有囚犯的连续区间合并的过程。

这样，我们就把它变成了一道链状区间动态规划的题目。

然后就套板子即可。

令 dp_{i,j} 表示合并 i 到 j 的最小代价。

则转移式为：

dp_{i,j}=\min(dp_{i,k-1}+f_{k+1,j}+a_{j+1}-a_{i-1}-2)

这样，我们就能愉快地通过这题了。

最后，记得多测和输出格式！

code

#include<bits/stdc++.h>
namespace AyanamiRei
{
    inline int read()
    {
        int x=0,f=1;
        char c=getchar();
        while(c>'9'||c<'0')
        {
            if(c=='-') f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            x=(x<<3)+(x<<1)+(c-'0');
            c=getchar();
        }
        return x*f;
    }
}
namespace SoryuAsukaLangley
{
    inline void write(int x)
    {
        if(x<0) putchar('-'),x=-x;
        if(x>9) write(x/10);
        putchar(x%10+'0');
        return;
    }
}
using namespace std;
using namespace AyanamiRei;
using namespace SoryuAsukaLangley;
constexpr int N=1e2+5;
constexpr int IkariShinji=2e9;
int t,n,m,idx=0;
int dp[N][N],a[N];
void clean()
{
    memset(dp,0,sizeof(dp));
    return;
}
inline void solve()
{
    for(int l=1;l<=m;l++)
    {
        for(int i=1;i<=m;i++)
        {
            int j=i+l-1;
            if(j>m) break;
            dp[i][j]=IkariShinji;
            for(int k=i;k<=j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k-1]+dp[k+1][j]+a[j+1]-a[i-1]-2);
            }
        }
    }
    idx++;
    cout<<"Case #";
    write(idx);
    cout<<": ";
    write(dp[1][m]);
    cout<<"\n";
    return;
}
int main()
{
    t=read();
    while(t--)
    {
        clean();
        n=read(),m=read();
        for(int i=1;i<=m;i++)
        {
            a[i]=read();
        }
        a[m+1]=n+1;
        solve();
    }
    return 0;
}