HLOJ430 쌍탑 구축

3689 단어 dp문제풀이듀얼 프로세스 DP

제목의 뜻


고정된 높이가 있는 네모난 덩어리로 두 개의 같은 높이의 탑을 쌓아 탑의 최고 높이를 물었다.

상태 이동 방정식


이중 프로세스 dp
f[j][k]는 한 탑의 높이가 j이고 다른 탑의 높이가 k인 경우 f[j][k]는 한 탑의 높이가 j이고 다른 탑의 높이가 k인 경우 존재하는지 여부를 나타낸다
우리는 쉽게 얻을 수 있다.
f[j][k]=f[j−a[i]][k]  ||  f[j][k−a[i]] f [ j ] [ k ] = f [ j − a [ i ] ] [ k ]     | |     f [ j ] [ k − a [ i ] ]

code

#include
using namespace std;
inline int read()
{
    int num = 0;
    char c = ' ';
    bool flag = true;
    for(;c > '9' || c < '0';c = getchar())
    if(c == '-')
    flag = false;
    for(;c >= '0' && c <= '9';num = num*10+c-48,c=getchar());
    return flag ? num : -num;
}
const int maxn=105;
int n,a[maxn],sum=0;
void init()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),sum+=a[i];
}
const int max_height=2020;
bool f[max_height][max_height];
void DP()
{
    f[0][0]=true;
    for(int i=1;i<=n;i++)
        for(int j=sum-a[i];j>=0;j--)
            for(int k=sum-a[i];k>=0;k--)
                if(f[j][k])
                {
                    f[j+a[i]][k]=f[j][k+a[i]]=true;
                }
    for(int i=sum/2;i>=1;i--)
        if(f[i][i])
        {
            printf("%d
",i);
            exit(0);
        }
    printf("Impossible
");
}
int main()
{
    init();
    DP();
    return 0;
}
React 101 - 파트 4: 이벤트 및 양식
반년 정도 일하면서 안드로이드 앱을 개발한 책이 유용해요.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage