zoj 3905 (dp + 스크롤 그룹)

Cake
Time Limit: 4 Seconds      
Memory Limit: 65536 KB
Alice and Bob like eating cake very much. One day, Alice and Bob went to a bakery and bought many cakes.
Now we know that they have bought n cakes in the bakery. Both of them like delicious cakes, but they evaluate the cakes as different values. So they decided to divide those cakes by following method.
Alice and Bob do n /2 steps, at each step, Alice choose 2 cakes, and Bob takes the cake that he evaluates it greater, and Alice take the rest cake.
Now Alice want to know the maximum sum of the value that she can get.

Input

The first line is an integer T which is the number of test cases.
For each test case, the first line is an integer n (1<=n<=800). Note that n is always an even integer.
In following n lines, each line contains two integers a[i] and b[i], where a[i] is the value of ith cake that Alice evaluates, and b[i] is the value of ith cake that Bob evaluates. (1<=a[i], b[i]<=1000000)
Note that a[1], a[2]..., a[n] are n distinct integers and b[1], b[2]..., b[n] are n distinct integers.

Output

For each test case, you need to output the maximum sum of the value that Alice can get in a line.

Sample Input

1
6
1 6
7 10
6 11
12 18
15 5
2 14

Sample Output

28

Author: 
HUA, Yiwei
Source: 
ZOJ Monthly, October 2015
월례 시합 때 또 하지 못해서 정말 속상하다.
제목:
n(n은 짝수) 케이크는 A와 B에게 똑같이 나누어져야 한다. A와 B는 모든 케이크에 대해 그들 자신의 마음속의 가치가 있다.그 다음에 이렇게 똑같이 나눈다. A는 그 중에서 2개를 골라서 B에게 선택하게 한다. B는 그가 가치가 더 높다고 생각하는 부분을 선택하고 다른 하나는 A에게 주고 상술한 조작을 반복해서 나누어질 때까지 한다.A가 얻을 수 있는 최대의 가치를 구하다.
분석:
사실 상태를 잘 정의할 수만 있다면 추이 방정식은 추론하기 어렵지 않다.상태를 정의할 때 방해도 배제해야 한다. 예를 들어 나는 처음에 항상 짝을 지어야 한다고 생각했다.
dp[i][j]는 전 i개의 케이크 중 A가 j개를 선택하여 얻은 가장 큰 합을 나타낸다. 방정식은'i개의 케이크를 취하든 안 취하든'에서 나온다.
code:
4

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define mod 1000000007
const int INF = 1<<30;
const int N = 810;
int dp[N][N];
pair<int,int> pr[N];
bool cmp(pair<int,int> i, pair<int,int> j) {return i>j;}
int main()
{
    int T, n;

    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            scanf("%d%d", &pr[i].S,&pr[i].F);
        sort(pr+1,pr+n+1,cmp); //                    
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=i/2; j++)
            {
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+pr[i].S);
            }
        }
        printf("%d
", dp[n][n/2]);
    }
    return 0;
}

각 층의 상태가 상층 상태에서 옮겨오는 것을 볼 수 있기 때문에 여기는 스크롤 수조로 1차원 공간을 줄일 수 있고 1차원을 반복적으로 이용하여 조작할 수 있다.2차원이라면 이전 과정이 상층에 영향을 주지 않고 1차원이라면 dp[j]=max(dp[j], dp[j-1]+...)를 볼 수 있다.이렇게 하면 사실 문제가 있다. 문제는 j상태를 갱신할 때 2차원 상층에 해당하는 j상태를 덮어쓰는 것이다. 그러면 j+1상태를 갱신할 때 원래의 j상태에서 옮겨온 것이 아니다.그래서 우리는 순환의 순서를 좀 돌려서 영향을 주지 않을 수 있다.
code:

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define mod 1000000007
const int INF = 1<<30;
const int N = 810;
int dp[N];
typedef pair<int,int> pii;
pii pr[N];
bool cmp(pii i, pii j) {return i>j;}
int main()
{
    int T, n;

    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i=1; i<=n; i++)
            scanf("%d%d", &pr[i].S,&pr[i].F);
        sort(pr+1,pr+n+1,cmp);
        memset(dp, 0, sizeof(dp));
        for(int i=1; i<=n; i++)
        {
            for(int j=i/2; j>=1; j--)
            {
                dp[j] = max(dp[j],dp[j-1]+pr[i].S);
            }
        }
        printf("%d
", dp[n/2]);
    }
    return 0;
}