BNU 11993 Soccer Teams(가방 변형 + 디지털 dp)

제목:
9개의 수를 제시하면 각각 a[i] 숫자 i가 있음을 나타낸다. 현재 이 숫자들은 모두 사용하지만 0을 추가할 수 있다.11정수의 수를 받을 수 있는 최소 자릿수가 얼마냐고 물었다.
문제 풀이:
01 가방의 변형은 디지털 dp 대위와 약간 비슷하다.dp[i][j]는 i위를 표시하고 이 위치의 화%11위 j, dp[i][j]가 계산한 것은 홀수 위치의 화합이 j인 상황을 나타낸다. 그 다음에 홀수 위치를 일일이 열거하여 짝수 위치를 얻어 짝수 위치의 최소치를 비교한다.

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int oo=0x3f3f3f3f;
const ll OO=1LL<<61;
const ll MOD= 1000000007;
const int maxn=105;
const int maxm=1005;
int a[10];
int dp[205][12];///  i           11 j      i j        

int main()
{
    int T,sum,cnt;
    scanf("%d",&T);
    while(T--)
    {
        sum=cnt=0;
        for(int i=1;i<=9;i++)
        {
            scanf("%d",&a[i]);
            cnt+=a[i];
            sum+=a[i]*i;
        }
        memset(dp,0,sizeof dp);
        ///01      
        dp[0][0]=1;
        for(int dig=1;dig<=9;dig++)
        {
            for(int t=1;t<=a[dig];t++)
            {
                for(int i=maxn-1;i>=0;i--)
                {
                    for(int j=0;j<11;j++)
                    {
                        if(dp[i][j])
                            dp[i+1][(j+dig)%11]=1;
                    }
                }
            }
        }
        int add=10000;///     
        for(int i=1;i<=cnt;i++)///     
        {
            for(int j=0;j<11;j++)
            if(dp[i][j])
            {
                if((sum%11-j-j)%11!=0)continue;
                int lt=cnt-i;
                if(i==lt)
                {
                    add=0;
                    break;
                }
                else
                {
                    add=min(add,abs(i-lt)-1);
                }
            }
        }
        if(add==10000)add=-cnt-1;
        printf("%d
",cnt+add);
    }
    return 0;
}
/***
200
100 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1
*/