第八周学习体会

第八周学习体会

这个周我们学习了区间dp和背包的有关知识，我觉得要想学好这两块的知识我们首先要多做这样类型的题才能熟练地运用这两块内容基本上固定的公式。费老师上课的时候对我们说的我课下也反思过，我的确应该多花点时间在知识的积累和做题上，这样才能最大程度上学好ACM这门课。

区间dp是求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。

区间dp的基本模板如下：

for(int len=1;len<=n;len++)
{//枚举长度for(int j=1;j+len<=n+1;j++){//枚举起点，ends<=nint ends=j+len-1;for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);}}
}

背包，它主要分为01背包，完全背包和多重背包。
1、01背包：它是给定N件重量为m[i]、价值为w[i]的物品和承重为V的背包，求在背包承重范围内接受物品的最大价值。他的特点是每种物品只有一件，只能选择放或者不放。
转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])。
还可以将其压缩到一维状态：
for(int i=1->n)
for(int j=v->1)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

2、完全背包：它也是给定N种重量为m[i]、价值为w[i]的物品和承重为V的背包，求在背包承重范围内接受物品的最大价值。它的特点是每种物品可以取若干件。
转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-m[i]]+w[i])。
借用01背包的思想，本次使用的转移方程也是只涉及到i-1的纵向级别。但与上面不同的是，此次考虑的对象是dp[i][j-v[i]]，所以我们必须让体积由前向后循环：
for(int i=1->n)
for(int j=1->v)
dp[j]=max(dp[j],dp[j-v[i]]+w[i])。

3、多重背包：它的问题的思路跟完全背包的思路非常类似，只是k的取值是有限制的，但是每件物品的数量是有限制的。
转移方程： dp[i][v] = max{dp[i - 1][v - k * c[i]] + w[i] | 0 <=k <= n[i]}
其中c[i]是物品的数量，和完全背包的不同支出在于完全背包可以取无数件，而多重背包给定了最多能取的数量。这样也是三个循环，分别是背包容量，物品个数和物品种类。

例题：
1.Halloween
Gappu has a very busy weekend ahead of him. Because, next weekend is Halloween, and he is planning to attend as many parties as he can. Since it’s Halloween, these parties are all costume parties, Gappu always selects his costumes in such a way that it blends with his friends, that is, when he is attending the party, arranged by his comic-book-fan friends, he will go with the costume of Superman, but when the party is arranged contest-buddies, he would go with the costume of ‘Chinese Postman’.

Since he is going to attend a number of parties on the Halloween night, and wear costumes accordingly, he will be changing his costumes a number of times. So, to make things a little easier, he may put on costumes one over another (that is he may wear the uniform for the postman, over the superman costume). Before each party he can take off some of the costumes, or wear a new one. That is, if he is wearing the Postman uniform over the Superman costume, and wants to go to a party in Superman costume, he can take off the Postman uniform, or he can wear a new Superman uniform. But, keep in mind that, Gappu doesn’t like to wear dresses without cleaning them first, so, after taking off the Postman uniform, he cannot use that again in the Halloween night, if he needs the Postman costume again, he will have to use a new one. He can take off any number of costumes, and if he takes off k of the costumes, that will be the last k ones (e.g. if he wears costume A before costume B, to take off A, first he has to remove B).

Given the parties and the costumes, find the minimum number of costumes Gappu will need in the Halloween night.

Input
Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case starts with a line containing an integer N (1 ≤ N ≤ 100) denoting the number of parties. Next line contains N integers, where the ith integer ci (1 ≤ ci ≤ 100) denotes the costume he will be wearing in party i. He will attend party 1 first, then party 2, and so on.

Output
For each case, print the case number and the minimum number of required costumes.

Sample Input
2
4
1 2 1 2
7
1 2 1 1 3 2 1

Sample Output
Case 1: 3
Case 2: 4

这道题问的是关于脱几件衣服的，我们可以反过来思考他要穿几件衣服才能满足需要的衣服数量最小，这样思考起来就比较容易。联系题目，最坏的结果是每遇到一天都新穿一件衣服。最优的情况是穿上一件衣服不用脱，因为在后来可以派上用场，这样就少新买一件衣服。按照这个思路我们可以找出状态转移方程： dp[i][j]=min(dp[i+1][k-1]+dp[k][j],dp[i][j])。

ac代码：

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
#define M 101
int dp[M][M];
int a[M];
int main()
{int T;cin>>T;int sum=T;while(T--){int N;cin>>N;for(int i=0;i<N;i++)cin>>a[i];memset(dp,0,sizeof(dp));for(int i=0;i<N;i++)for(int j=i;j<N;j++)dp[i][j]=j-i+1;for(int j=0;j<N;j++)for(int i=j;i>=0;i--){dp[i][j]=dp[i+1][j]+1;for(int k=i+1;k<=j;k++){if(a[i]==a[k])dp[i][j]=min(dp[i+1][k-1]+dp[k][j],dp[i][j]);}}cout<<"Case "<<sum-T<<": "<<dp[0][N-1]<<endl;}
}

2.括号匹配
We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.
no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input
The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output
For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input
((()))
()()()
([]])
)[)(
([][][)
end
Sample Output
6
6
4
0
6

这道题可以分为两种情况，第一种情况是前面的括号和后面的括号恰好匹配，状态转移方程就是dp[i][j]=dp[i+1][j-1]+2;第二种情况是吐过括号不匹配时，就可以将该序列分成两个区间，比较dp[i][k]+dp[k+1][j]和dp[i][j]的大小关系。把较大的值赋给dp[i][j]。

ac代码：

#include<iostream>
#include<cmath>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
#define M 101
int dp[M][M];
char a[M];
int main()
{while(gets(a+1)){if(a[1]=='e') break;memset(dp,0,sizeof(dp));int n=strlen(a+1);for(int len=2;len<=n;len++){for(int i=1,j=len;j<=n;i++,j++){if((a[i]=='('&&a[j]==')')||(a[i]=='['&&a[j]==']'))dp[i][j]=dp[i+1][j-1]+2;for(int k=i;k<j;k++)dp[i][j]=max(dp[i][k]+dp[k+1][j],dp[i][j]);}}cout<<dp[1][n]<<endl;}return 0;
}

生死看淡，不服就干