vijos 적목성 동태 기획

묘사
XC의 아들 어린 XC가 가장 좋아하는 게임은 나무로 예쁜 성을 쌓는다.성곽은 입방체의 적목으로 쌓아서 성곽의 층층이 하나의 적목이다.작은 XC는 그의 아버지 XC보다 더 똑똑한 아이였다. 그는 성을 쌓을 때 아래의 적목이 위의 적목보다 크면 성이 쉽게 쓰러지지 않는다는 것을 발견했다.그래서 그는 성곽을 쌓을 때 항상 이런 규칙을 따른다.
어린 XC는 자신이 쌓은 성곽을 유치원에 있는 예쁜 여자 아이들에게 주고 싶어서 그의 호감도를 높일 수 있다.공평하게 하기 위해서, 그는 모든 여자 아이들처럼 높은 성곽에 보내기로 결정했다. 이렇게 하면 여자 아이들이 더욱 아름다운 성곽을 얻기 위해 다투는 것을 피할 수 있다.그러나 그는 자신이 성을 쌓고 있을 때 이 점을 미리 고려하지 않았다는 것을 발견했다.그래서 그는 지금 성곽을 개조하려고 한다.그는 남은 적목이 없기 때문에, 영감이 떠올라 교묘한 개조 방안을 생각해냈다.그는 모든 성에서 나무를 옮기기로 결정해서 결국 모든 성곽이 똑같이 높아졌다.그의 성곽을 더욱 웅장하게 하기 위해서, 그는 마지막 성곽을 가능한 한 높게 해야 한다고 느꼈다.
퀘스트: 작은 XC가 프로그램을 짜서 그가 쌓은 모든 성곽의 정보에 따라 어떤 나무를 옮겨야 가장 좋은 효과를 얻을 수 있는지 결정하세요.
서식
입력 형식
첫 번째 줄은 모두 몇 개의 성이 있음을 나타내는 정수 N(N<=100)이다.다음 N행의 각 행은 일련의 비 마이너스 정수로 한 칸의 빈칸으로 구분하고 아래에서 위로 순서대로 한 성곽의 모든 적목의 모서리 길이를 제시한다.-1로 끝내다.성 안의 적목은 100개를 넘지 않고, 각 적목의 모서리는 100개를 넘지 않는다.
출력 형식
마지막 성곽의 최대 가능한 높이를 나타내는 정수적당한 방안을 찾지 못하면 0을 출력합니다.
예제 1
샘플 입력 1[복사]

2
2 1 –1
3 2 1 –1

샘플 출력 1[복사]

3

프롬프트
원 데이터가 잘못되었는데, 내가 수정한 것이 맞는지 모르겠다.
출처
NlogN 년 전 저장성 팀 선발 X라운드
문제풀이의 방향
모든 성곽이 도달할 수 있는 높이를 구한 다음에 하나의 수조로 높이가 i인 성곽을 몇 개 저장하면 도달할 수 있다. 거꾸로 가장 큰 공통 높이를 찾으면 된다. 각 성곽이 도달할 수 있는 각종 높이를 구할 때 동적 계획을 사용한다.이 탑이 앞에 i-1개의 적목이 고도 j에 도달할 수 있을 때, 그는 i개의 나무토막에서 반드시 고도 j+a[i]에 도달할 수 있다.
코드

#include 
#include 
#include 
#include 
using namespace std;
const int INF=0x3f3f3f3f;
int n;
int a[110];//       
int ans[10010];//   i         
bool hight[10010];//          i
int main()
{
    int i,t;
    scanf("%d",&n);
    for(t=1;t<=n;++t)
    {
        int j,m=0;
        int maxhight=0;//             ；
        int h;

        memset(hight,0,sizeof(hight));
        hight[0]=1;
        scanf("%d",&h);

        while(h!=-1)
        {
            a[++m]=h;
           // hight[h]=1;//          ，  ，          , 1,3,5.     hight[2]=1 hight[1]=1,  hight[1+a[1]]=1
            maxhight+=h;
            scanf("%d",&h);
        }

        for(i=1;i<=m;++i)
        {
            for(j=maxhight-a[i];j>=0;--j)
                if(hight[j]) hight[j+a[i]]=1;
        }
        for(i=0;i<=maxhight;++i)
            if(hight[i]) ans[i]++;
    }
    //         
    for(i=10005;i>=0;--i)
        if(ans[i]==n)
        {
            printf("%d",i);
            break;
        }
    return 0;
}