| Time Limit: 4000ms, Special Time Limit:10000ms, Memory Limit:65536KB |
| Total submit users: 11, Accepted users: 9 |
| Problem 13240 : No special judgement |
| Problem description |
|
A long art gallery has 2N rooms. The gallery is laid out as N rows of 2 rooms side-by-side. Doors connect all adjacent rooms (north-south and east-west, but not diagonally). The curator has been told that she must close off k of the rooms because of staffing
|
| Input |
|
Input will consist of multiple problem instances (galleries). Each problem instance will begin with a line containing two integers N and k, where 3 ≤ N ≤ 200 gives the number of rows, and 0 ≤ k ≤ N gives the number of rooms that must be closed off. This |
| Output |
|
For each gallery, output the amount of value that the general public may optimally receive, one line per gallery. |
| Sample Input |
6 4 3 1 2 1 1 2 1 3 3 3 0 0 4 3 3 4 1 1 1 1 5 6 10 5 7 8 4 9 3 7 5 9 7 2 10 3 0 10 3 2 6 3 7 9 0 0 |
| Sample Output |
17 17 102 |
| Problem Source |
| ACM-ICPC North America Qualifier 2014 |
我还是很弱的……
dp[i][j][k]:前i行在状态j时，关掉k个房间后的最大值
当然有些k在某些状态时是访问不到的，所以此时赋上一个很小的值，这样就不影响结果
j是有3个状态，0为i行两个都取不到，1为关掉i行左边那个房间，2为关掉i行右边那个房间
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
#include<stack>
#include<set>
using namespace std;
int dp[210][3][210],k,n,g[210][2];
int work()
{
for(int i=0;i<3;i++)
fill(dp[0][i],dp[0][i]+k+1,INT_MIN);
dp[0][0][0]=g[0][0]+g[0][1];
dp[0][1][1]=g[0][1];
dp[0][2][1]=g[0][0];
for(int i=1;i<n;i++)
for(int j=0;j<=k;j++)
{
dp[i][0][j]=max(dp[i-1][0][j],max(dp[i-1][1][j],dp[i-1][2][j]))+g[i][0]+g[i][1];
if(j==0)
dp[i][1][j]=dp[i][2][j]=INT_MIN;
else
{
dp[i][1][j]=max(dp[i-1][0][j-1],dp[i-1][1][j-1])+g[i][1];
dp[i][2][j]=max(dp[i-1][0][j-1],dp[i-1][2][j-1])+g[i][0];
}
}
return max(dp[n-1][0][k],max(dp[n-1][1][k],dp[n-1][2][k]));
}
int main()
{
while(cin>>n>>k)
{
if(n==0&&k==0)
break;
for(int i=0;i<n;i++)
for(int j=0;j<2;j++)
cin>>g[i][j];
cout<<work()<<endl;
}
}