hdu 4381 Grid [약간 복잡 한 가방]

오래 끌 었 던 문제 = = 지난 수요일 부터 목요일 까지 생각 을 못 하고 컨디션 이 나 빠 서 주말 까지 공 부 를 못 했 어 요 = = 한 달 가까이 Dp 특집 의 마 무 리 를 지 운 셈 이 죠. 어려워 요. 어려워 요. T ^ T
제목: 한 열 에 n 개의 격자 m 회 조작 이 있 으 면 특정한 구간 의 x 개의 칸 을 흰색 으로 칠 할 수 있 습 니 다. 마지막 에 최대 몇 개의 흰색 이 있 느 냐 고 물 습 니 다 = =
가방 이랑 어떻게 관련 이 있 을 지 정말 몰랐어 요.상태 가 좋 지 않 기 때문에 오랫동안 문 제 를 풀 고 나 서 야 문제 의 구간 이 반드시 두 개의 단점 에서 시작 되 었 다 는 것 을 알 게 되 었 다. 그러면 이 성질 을 이용 하여 X 의 색칠 이 모두 단점 에서 시작 되 고 끊 이지 않 으 며 얼마나 가방 같 은 지 가정 할 수 있다.그럼 어떻게 쓰 지?
우선, 끊 임 없 는 색칠 인지 확인 되 었 으 니, 아래 표 시 는 몇 개의 색칠 이 있 는 지 직접 반영 할 수 있 습 니 다. dp 배열 은 조작 횟수 가 필요 합 니 다 ~ 첫 번 째 질문 에 대한 색칠 개 수 는 두 배열 의 아래 표 와 일치 하 는 것 입 니 다.두 번 째 질문: Dp 값 과 최소 값 을 구하 면 되 잖 아 요.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int maxn = 2005;
struct node{
    int aa,cor;
    node(){}
    node(int _aa,int _cor){
       aa = _aa;   cor = _cor;
    }
}x1[maxn],x2[maxn];
int n,m;
int dp1[maxn],dp2[maxn];
int sumx1,sumx2;

bool cmp(const node &p,const node &q){
    return p.aa < q.aa;
}

int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int cas,ta=1;
    scanf("%d",&cas);
    while(cas--){
         int i,j;
         scanf("%d%d",&n,&m);

         sumx1 = sumx2 = 1;
         for(i=0; i<m; i++){
             int key,yy,z;
             scanf("%d%d%d",&key,&yy,&z);
             if(key == 1){
                x1[sumx1++] = node(yy,z);
             }else{
                x2[sumx2++] = node(n+1-yy,z);
             }
         }
         sort(x1+1,x1+sumx1,cmp);
         sort(x2+1,x2+sumx2,cmp);
         memset(dp1,0x3f,sizeof(dp1));
         memset(dp2,0x3f,sizeof(dp2));

         dp1[0] = dp2[0] = 0;
         for(i=1; i<sumx1; i++){
             for(j=x1[i].aa; j>=x1[i].cor; j--){
                dp1[j] = min(dp1[j],dp1[j-x1[i].cor]+1);
             }
         }

         for(i=1; i<sumx2; i++){
             for(j=x2[i].aa; j>=x2[i].cor; j--){
                dp2[j] = min(dp2[j],dp2[j-x2[i].cor]+1);
             }
         }

         int ans = 0,anssum = 0,tmp;
         for(i=1; i<=n; i++){
            for(j=0; j<=i; j++){
               tmp = dp1[j] + dp2[i-j];
               if(tmp <= m){
                  if(ans != i){
                    ans = i;   anssum = tmp;
                  }else if(tmp < anssum){
                      anssum = tmp;
                  }
               }
            }
         }

         printf("Case %d: %d %d
",ta++,ans,anssum);
    }
    return 0;
}

P。S。 주말 정 비 를 마 쳤 지만 오늘 오후의 상 태 는 레저 에서 벗 어 나 지 못 했 습 니 다. T ^ T. 오늘 밤 정상 궤도 에 오 를 수 있 을 것 같 습 니 다.주말 을 앞 두 고 룸메이트 와 중학교 이 야 기 를 나 눈 기억 이 납 니 다. 실 장님 으로 부터 어린 시절 이 라 고 평 가 받 았 습 니 다. 중학교 와 고등학교 가 모두 없어 졌 기 때 문 이 라 고 평 가 받 았 습 니 다. 한편 으로 는 중학교 의 엄격 한 교육 이 가 져 온 성적 에 감 사 드 리 고, 다른 한편 으로 는 그런 교육 이 저 를 이렇게 뻔뻔 하 게 살 게 해 준 것 에 감 사 드 립 니 다.첫 번 째 단체 활동 (노동절 이 든 11 일 이 든 홍수 방지 기념 탑 에서 의 학교 축제 이브 닝 파티 든 무슨 파티 든 어차피 관중 이 되 어야 한다) 원래 낮 에 가족 들 과 놀 러 가 야 하 는데 제시간에 돌아 오지 못 하고 담임 선생님 과 휴가 를 내 서 지적 을 받 았 다. 수학 시험 7, 8 점 은 재미있게 놀 러 갈 수 있다!고등학교 때 출입증 빌려 주 고 들 키 면 담임 선생님 이 계단 에서 소리 지 르 는 반 전체 가 방 에서 다 들 려 요. 어쨌든 대학 에 들 어간 후 유리 마음 은 체면 문제 로 인해 자주 자신 과 어 울 리 지 못 할 것 같 지만 지나 가면 지나 간다.
내년 봄 에 남 을 수 있 을 지, 내년 가을 에 제대로 취직 할 수 있 을 지 걱정 입 니 다. 강북 에 대한 희망 이 있 었 는데 마지막 퇴로 로 (대학원 진학 은 불가능 합 니 다 = =) 집 이 강북 에 있 으 면 사업 장 에 사람 을 구 하 는 것 같 습 니 다. T ^ T 그래도 IT 회사 에 가서 전단 개발 을 하고 싶 습 니 다. T ^ T ""이 일 은 별로 쓸모 가 없 으 니 자신 이 선택 한 방향 으로 노력 하 세 요. 지난주 에 시 진 핑 에서 말 하 는 사상 선생님 께 서 대학 3 학년 때 부터 이력 서 를 작성 하기 시작 했다 고 하 셨 는데 위 에서 'ACM 지역 경기 동메달 이 무슨 소 용이 있 습 니까?' 라 고 묻 는 것 을 연상 시 켰 습 니 다.맨 아래 의 대답 은 저 에 게 만 개의 찬 사 를 주 고 싶 습 니 다. 지역 경기 동메달 은 한 줄 뿐 입 니 다. 아마 많은 사람들의 대학 4 년 일 것 입 니 다. 화 이 팅 하 세 요. 1 년도 안 남 았 습 니 다. 자기 야, 자신 만 감동 시 키 지 말고 지금 좀 더 노력 하고 힘 들 게 하 세 요. 내년 가을 에 눈 하나 덜 받 고 offer 하나 더 받 으 세 요.