区间动态规划

今天谜一样的把区间动态规划给敲完了QAQ，好累……特地来总结一下！

区间动态规划就是针对一个区间，进行从小区间推到大区间，而大区间的值来自于小区间，一般是有三重循环，最外面枚举区间长度，从2开始，另一个循环开始枚举出发点，然后结尾就可以计算出来，最后枚举在i到j中选择分割点来分割成两个小区间来更新i到j这个大区间。区间DP在乎的是区间成体的最优值。

然后区间DP的题并不水，要比昨天的题目要难一些的，所以还需要多多复习一下！PS：（省选之前复习一下所有学过的模板，感觉已经忘光了QAQ）。

P1290关灯

题目描述：

宁智贤得到了一份有趣而高薪的工作。每天早晨她必须关掉她所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。 宁智贤每晚到早晨5点钟都在晚会上，然后她开始关灯。开始时，她站在某一盏路灯的旁边。 每盏灯都有一个给定功率的电灯泡，因为宁智贤有着自觉的节能意识，她希望在耗能总数最少的情况下将所有的灯关掉。 宁智贤因为太累了，所以只能以1m/s的速度行走。关灯不需要花费额外的时间，因为当她通过时就能将灯关掉。 编写程序，计算在给定路灯设置，灯泡功率以及宁智贤的起始位置的情况下关掉所有的灯需耗费的最小能量。

输入：

  1. 第一行包含一个整数N，2≤N≤1000，表示该村庄路灯的数量。
  2. 第二行包含一个整数V，1≤V≤N，表示宁智贤开始关灯的路灯号码。
  3. 接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每盏灯的参数，其中0≤D≤1000，0≤W≤1000。D表示该路灯与村庄开始处的距离(用米为单位来表示)，W表示灯泡的功率，即在每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。

输出：

第一行即唯一的一行应包含一个整数，即消耗能量之和的最小值。注意结果小超过1,000,000,000

题解：

这道题是一道比较好的区间动态规划的题目，我那道题之后，就开始各种无脑猜测，结果，结果什么都没有猜出来，全被自己否决了。最后被逼无奈的看了题解（以后要注重自己的思维性的培养，少看题解！）。题解大概是这样解题的。

注：下面所有的i，j表示的是灯的序数并非横坐标。

我们首先列出来状态设置，首先因为是区间动态规划，所以说我们可以建立一个数组 f[i][j] 表示关掉区域i到j的所有灯所需要消耗的最少电，但是推来推去，就是无法得出正确的状态转移方程，所以说我们还需要进行各种无脑猜测，因为在实际的状态中我们在进行从小推到大的时候，关掉子区域i到k和关掉子区域k到j的过程中，两个子区域关闭之后，人在左端还是右端是会影响最后的答案的，有可能位于左端的时候会比在右端的时候多走一些等待路程（其过程消耗功率是相同的，所以就多了消耗些电）。

那么我们就需要增加一个维度了，开一个数组 f[i][j][k] 表示在关掉区域i到j所有灯的时候，最后停留在k端所消耗的最小电能（当k==1的时候为右段，k==0的时候为左端）。然后我们分别计算在位于左端和右端的时候的最优值。
我们就开始分析状态的转移，我们知道 f[i][j] 的关系只和 f[i+1][j] 和 f[i][j-1] 有关 (f[i][j] 的一个子区域) ，那么我们就可以通过 f[i][j] 和 f[i+1][j] 和 f[i][j-1] 里面选择并推导出来 f[i][j] ，因为还有左端和右端的关系，所以一共从四种情况中选择出来两种进行更新。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
using namespace std;
struct Light
{
    int Way;
    int Electricity;
}a[1001];
bool mycmp(Light a,Light b)
{ return a.Way<b.Way; }
int n,Start,f[1001][1001][2];
int Get[1001][1001],xx,yy;
int main()
{
    memset(f,10,sizeof(f));
    memset(Get,0,sizeof(Get));
    cin>>n>>Start;
    for(int i=1;i<=n;i++)
    cin>>a[i].Way>>a[i].Electricity;
    sort(a+1,a+1+n,mycmp);
    for(int i=2;i<=n;i++)
    a[i].Electricity+=a[i-1].Electricity;
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    Get[i][j]=a[n].Electricity+a[i-1].Electricity-a[j].Electricity;
    f[Start][Start][1]=0;
    f[Start][Start][0]=0;
    for(int p=2;p<=n;p++)
    for(int i=1;i<=n;i++)
    {
        int j=i+p-1;
        if(j>n) break;
        xx=f[i+1][j][0]+(a[i+1].Way-a[i].Way)*Get[i+1][j];
        yy=f[i+1][j][1]+(a[j].Way-a[i].Way)*Get[i+1][j];
        f[i][j][0]=min(xx,yy);
        xx=f[i][j-1][0]+(a[j].Way-a[i].Way)*Get[i][j-1];
        yy=f[i][j-1][1]+(a[j].Way-a[j-1].Way)*Get[i][j-1];
        f[i][j][1]=min(xx,yy);
    }
    cout<<min(f[1][n][0],f[1][n][1])<<endl;
    return 0;
}

P1291添加括号

题目描述：

给定一个正整数序列a(1)，a(2)，…，a(n),(1<=n<=20) 不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。 例如: 给出序列是4，1，2，3。 第一种添括号方法: ((4+1)+(2+3))=((5)+(5))=(10) 有三个中间和是5，5，10，它们之和为:5+5+10=20 第二种添括号方法 (4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10) 中间和是3，6，10，它们之和为19。

输入：

共两行。 第一行，为整数n。(1<=n<=20) 第二行，为a(1),a(2),…,a(n)这n个正整数，每个数字不超过100。

输出：

输出3行。 第一行，为添加括号的方法。 第二行，为最终的中间和之和。 第三行，为n-1个中间和，按照从里到外，从左到右的顺序输出。

题解：

这道题的第一问其实并不难，仅仅只是一个很典型的区间DP而已，我们直接建立一个f[i][j]数组表示i和j之间的数用大括号括起来的所有权值大小，然后进行一个分区枚举k，表示f[i][k]加上f[k+1][j]的权值不断更新f[i][j]，这样做之所以会成立是因为扩号要求扩出来的里面必须要有两个元素（扩号里面的算一个单独元素），所以说我们这样直接枚举连个元素进行括起来，然后更新值就能得出最优答案。

但难的地方就是在于最后答案的输出，因为这些并不是按照顺序的，所以最后我们需要按照题目要求的顺序输出，那么我们新建一个数组cut[i][j]存储着一个k值，表示的是在更新i到j的最优值的时候，是依靠f[i][k]和f[k+1][j]来更新f[i][j]的，然后用DFS进行输出，

1
2
3
4
5
6
7
8
9
10
11
12
13
void First_out(int i,int j)
{
    if(i>=j)
    {
        cout<<a[i];
        return;
    }
    cout<<"(";
    First_out(i,cut[i][j]);
    cout<<"+";
    First_out(cut[i][j]+1,j);
    cout<<")";
}

这里用cut存储的值，不断将区间折断，并输出“ ( ”，一直到最初的两个区间之后，开始输出区间里左半部分的值，然后开始输出相同优先级别的大括号，然后再次进行递归，不停地补充右半部分，最后完成；

1
2
3
4
5
6
7
void Second_out(int i,int j)
{
    if(i>=j) return;
    Second_out(i,cut[i][j]);
    Second_out(cut[i][j]+1,j);
    cout<<Get[j]-Get[i-1]<<' ';
}

这里的本质和上面是一样的，同样是进行先输出左半部分，然后输出右半部分（因为从里到外，从左到右）。

好了，这道题我们就愉快的AC了QAQ

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
int n,a[100],f[100][100];
int cut[100][100],mini,Get[100];
void First_out(int i,int j)
{
    if(i>=j)
    {
        cout<<a[i];
        return;
    }
    cout<<"(";
    First_out(i,cut[i][j]);
    cout<<"+";
    First_out(cut[i][j]+1,j);
    cout<<")";
}
void Second_out(int i,int j)
{
    if(i>=j) return;
    Second_out(i,cut[i][j]);
    Second_out(cut[i][j]+1,j);
    cout<<Get[j]-Get[i-1]<<' ';
}
int main()
{
    memset(f,10,sizeof(f));
    memset(Get,0,sizeof(Get));
    memset(cut,0,sizeof(cut));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        Get[i]=a[i]+Get[i-1];
        f[i][i]=0;
        cut[i][i]=i;
    }
    for(int k=2;k<=n;k++)
    for(int i=1;i<=n;i++)
    {
        int j=i+k-1;
        if(j>n) break;
        for(int k=i;k<j;k++)
        if(f[i][k]+f[k+1][j]<=f[i][j])
        {
            f[i][j]=f[i][k]+f[k+1][j];
            mini=k;
        }
        cut[i][j]=mini;
        f[i][j]=f[i][j]+Get[j]-Get[i-1];
    }
    First_out(1,n);
    cout<<endl<<f[1][n]<<endl;
    Second_out(1,n);
    return 0;
}

P1292监狱

题目描述：

  • 小X的王国中有一个奇怪的监狱，这个监狱一共有P个牢房，这些牢房一字排开，第i个仅挨着第i+1个（最后一个除外），当然第i个也挨着第i-1个（第一个除外），现在牢房正好是满员的。
  • 上级下发了一个释放名单，要求每天释放名单上的一个人。这可把看守们吓得不轻，因为看守们知道，现在牢房里的P个人，可以相互之间传话。第i个人可以把话传给第i+1个，当然也能传给第i-1个，并且犯人很乐意把消息传递下去。
  • 如果某个人离开了，那么原来和这个人能说上话的人，都会很气愤，导致他们那天会一直大吼大叫，搞得看守很头疼。如果给这些要发火的人吃上肉，他们就会安静下来。为了河蟹社会，现在看守们想知道，如何安排释放的顺序，才能是的他们消耗的肉钱最少。

输入：

  1. 第一行两个数P和Q，Q表示释放名单上的人数；
  2. 第二行Q个数，表示要释放哪些人。

输出：

仅一行，表示最少要给多少人次送肉吃。

题解：

对于这道题我也是想了好久好久好久的说，首先我们可以这样来想，监狱里面一共有m个需要出来，每出来一个人，周围相连的人就需要喂肉肉，那么我们就可以这样进行计算，计算区间i到j的人离开之后需要喂肉肉的最小值。

我们来进行一个非常重要的预处理，这个预处理就是用来计算当一个人逃离出来监狱之后，其他的监友需要吃到的肉，也就是两个要出走的人之间的距离，我们建一个一维数组Get[i]最终这个数组表示的将是释放前i个人需要支付的肉肉之和，对于区间3,4用Get来计算出来第3个人插入的时候最小值，具体处理方法如下：

1
2
3
4
5
6
for(int i=1;i<=m;i++)
{
    Get[i]=a[i]-a[i-1]-1;
    Get[i]+=Get[i-1];
}
Get[m+1]=n-a[m]+Get[m];

这个处理出来之后，我们就可以轻易的知道第几个人插入的时候的值了，然后设置状态 f[i][j] 表示第i个人到j个人（不包括）插入需要的最小值，比如 f[1][2] 就表示1离开需要喂肉肉的最小值，这样在进行区间合并的时候，就可以这样：f[1][4]=f[1][2]+f[3][4]+Get ;

解释一下就是 f[1][4] 表示的是从1到3这三个人脱离之后的最小喂肉肉值，就是第1个人拖出来然后去喂肉肉的最小值加上第3个人拖出来然后去喂肉肉的最小值之后，还需要加上中间的那个人，也就是第三重循环枚举的第k个人，只有第k（3）个人最先拖出来砍掉，其他的第1个人和第3个人才能运用出来最优解，而Get的求法（第k个人出来需要给其他人喂肉肉的最小值）就是 Get[4]-Get[1-1]+4-1-1 （ Get[j]-Get[i-1]+j-i-1 ）；其中Get在处理的时候忽略掉了要出去的人（最优值），但是第k个人先出去的时候，其他要出去的人还没有出去，所以不能忽略，那么就需要加上去，也就是 j-i-1=2 （两个人，第1个人和第3个人），那么状态转移方程就出来了：

1
f[i][j]=min(f[i][j], f[i][k]+f[k+1][j]+Get[j]-Get[i-1]+j-i-1);

这一类型的题目还是需要多想想，多练练，在动态规划中预处理非常重要，有些方程如果没有预处理就无法进行计算。好多明明想出来了状态转移方程了，但是由于无法计算出来状态转移方程中的具体值，那么最后导致不得不放弃最后的方程，陷入无解状态，所以说以后做题需要仔细想一想中间看似不能求解的值，最后能否可以通过预处理进行求出来，然后在状态转移方程中用出来。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[1001],f[1001][1001];
int Get[1001],now;
int main()
{
    memset(f,10,sizeof(f));
    memset(Get,0,sizeof(Get));
    memset(a,0,sizeof(a));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+m+1);
    f[0][0]=0;
    f[m+1][m+1]=0;
    for(int i=1;i<=m;i++)
    {
        f[i][i]=0;
        Get[i]=a[i]-a[i-1]-1;
        Get[i]+=Get[i-1];
    }
    Get[m+1]=n-a[m]+Get[m];
    for(int i=1;i<=m+1;i++)
    for(int i=m+1;i>=1;i--)
    for(int j=i+1;j<=m+1;j++)
    for(int k=i;k<j;k++)
    f[i][j]=min(f[i][j], f[i][k]+f[k+1][j]+Get[j]-Get[i-1]+j-i-1);
    cout<<f[1][m+1]<<endl;
    return 0;
}