YJ's Salesman HDU - 6447(dp+ 세그먼트 트리 최적화)

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination. One day, he is going to travel from city A to southeastern city B. Let us assume that A is (0,0)(0,0) on the rectangle map and B (109,109)(109,109). YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at (x,y)(x,y) now (0≤x≤109,0≤y≤109)(0≤x≤109,0≤y≤109), he will only forward to (x+1,y)(x+1,y), (x,y+1)(x,y+1) or (x+1,y+1)(x+1,y+1). On the rectangle map from (0,0)(0,0) to (109,109)(109,109), there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a village kk on (xk,yk)(xk,yk) (1≤xk≤109,1≤yk≤109)(1≤xk≤109,1≤yk≤109), only the one who was from (xk−1,yk−1)(xk−1,yk−1) to (xk,yk)(xk,yk) will be able to earn vkvk dollars.(YJJ may get different number of dollars from different village.) YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.
Input
The first line of the input contains an integer TT (1≤T≤10)(1≤T≤10),which is the number of test cases. In each case, the first line of the input contains an integer NN (1≤N≤105)(1≤N≤105).The following NN lines, the kk-th line contains 3 integers, xk,yk,vkxk,yk,vk (0≤vk≤103)(0≤vk≤103), which indicate that there is a village on (xk,yk)(xk,yk) and he can get vkvk dollars in that village. The positions of each village is distinct.
Output
The maximum of dollars YJJ can get.
Sample Input

Sample Output

사고방식: 먼저 행렬에서 이동하는 dp, dp[i][j]=max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+v[i][j])를 연상할 수 있다. 우선 이산화는 필연적이다.
그 다음에 이런 2차원 그룹은 열 수 없다(1e5*1e5가 공간이 터졌기 때문에) 먼저 1차원 스크롤을 고려한다. dp[j]는 j열이 얻을 수 있는 최대치를 나타낸다. 한 가지 확실한 것은 같은 열에 있는 점은 하나만 선택하여 거래를 할 수 있다는 것이다.그래서 가로 좌표 순서에 따라 한 번 선택하는 것이 가장 좋은 전략이기 때문에 i를 스크롤합니다.
이어서 i열의 최대 값은 전 i행의 어떤 열에서 나올 수 있기 때문에 라인 트리로 전 j-1열의 최대 값을 유지하는 것을 고려할 수 있습니다.(세그먼트 나무를 쓰지 않고 직접 만들어도 물이 지나갈 수 있다고 한다).
이산화 후 x는 작은 것부터 큰 것까지, y는 큰 것부터 작은 것까지 정렬한다(01배낭의 스크롤 그룹 원리와 유사하여 역순으로 구해야 한다).그런 다음 업데이트하면서 조회하면 된다.
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int maxn=1e5+7;
#define Lson l,m,rt<<1
#define Rson m+1,r,rt<<1|1
struct Point
{
    int x,y,w;
}p[maxn];
bool cmp(Point a,Point b)
{
    if(a.x==b.x) return a.y>b.y;
    return a.x>1;
    Build(Lson);
    Build(Rson);
}
void push_up(int rt)
{
    tree[rt].Max=max(tree[rt<<1].Max,tree[rt<<1|1].Max);
}
void updata(int pos,int v,int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt].Max=max(v,tree[rt].Max);
        return;
    }
    int m=(l+r)>>1;
    if(pos>m) updata(pos,v,Rson);
    else updata(pos,v,Lson);
    push_up(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        return tree[rt].Max;
    }
    int m=(l+r)>>1;
    int ans1=0,ans2=0;
    if(R>m) ans1=query(L,R,Rson);
    if(L>T;
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].w);
            hash_x[i]=p[i].x,hash_y[i]=p[i].y;
        }
        sort(hash_x+1,hash_x+n+1);
        sort(hash_y+1,hash_y+n+1);
        int n1=unique(hash_x+1,hash_x+1+n)-hash_x-1;
        int n2=unique(hash_y+1,hash_y+1+n)-hash_y-1;
        for(int i=1;i<=n;i++)
        {
            p[i].x=lower_bound(hash_x+1,hash_x+1+n1,p[i].x)-hash_x;
            p[i].y=lower_bound(hash_y+1,hash_y+1+n2,p[i].y)-hash_y;
        }
        sort(p+1,p+1+n,cmp);
        int ans=0;
        Build(1,n,1);
        for(int i=1;i<=n;i++)
        {
            int tmp=0;
            if(p[i].y==1) tmp=p[i].w;
            else tmp=query(1,p[i].y-1,1,n,1)+p[i].w;
            updata(p[i].y,tmp,1,n,1);
            ans=max(ans,tmp);
        }
        printf("%d
",ans);
    }
    return 0;
}

YJ's Salesman HDU - 6447(dp+ 세그먼트 트리 최적화)

좋은 웹페이지 즐겨찾기