ACM-ICPC 2017 Asia Xi'an——LOL(DP)

제목:

게임 LOL 패러디, 자기측이 영웅 5개를 선택(선택할 수 있는 전제는 이미 이 영웅을 샀다는 것이다)
자기편이 뽑은 영웅은 똑같을 수 없다. 적도 다섯 명의 영웅을 뽑지만 좋아하는 사람을 마음대로 뽑을 수 있다. 그리고 적과 적은 각각 다섯 명의 영웅을 금지할 수 있다. 총 영웅 종류는 100개다.
문제 풀이:
제목의 뜻을 주어진 입력 데이터로 구체화하는 것은 5줄에 0과 1만 구성된 문자열을 주고 한 줄에 1을 선택하고 각 줄에 1을 선택하면 같은 열에 있을 수 없다.
DP로 할 수 있다. 먼저 첫 줄의 선택할 수 있는 방안을 처리한다. 즉, 첫 줄 1의 개수를 처리한 다음에 다음 2~5줄에서 앞의 선택에 따라 자신을 선택한다. 열수가 같고 선택한 줄의 수가 다르기 때문에 우리는 다섯 줄의 수를 모두 배열한다. 이렇게 하면 자기측이 선택할 수 있는 방안이 나온다. 이것은 끝이 아니다. 왜냐하면 모두가 선택한 일치 방안이기 때문이다.그래서 적들이 선택할 수 있는 영웅 방안과 모두가 금지하는 영웅 방안을 덧붙여서 다음과 같이 표시한다. A(95,5)*C(90,5)*C(85,5)(식 대표: 지방은 자기측이 5명을 선택한 후 남은 사람 중 5개를 선택하고 선택한 순서가 다르면 다른 방안이다. 그래서 배열로 표시하고 그 다음에 양쪽 모두 금지할 영웅 순서를 선택해야 하기 때문에 조합수로 표시한다)자기측이 선택할 수 있는 방안으로 이 수를 곱하기만 하면 답을 얻을 수 있다.
DP 전이 방정식: dp[i][j]=dp[i][j]+dp[i-1][j-1];
제목은 계마늘꾼에서 유래했다
코드 구현:

#include

using namespace std;
typedef long long ll;
const ll mod=1e9+7;
char s[6][105];
ll dp[6][105],ans;
void ini(int t)
{
    if(t==5)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=100;i++)
        {
            dp[1][i]=dp[1][i-1];
            if(s[1][i]=='1')
                dp[1][i]++;
        }
        for(int i=2;i<=5;i++)
        {
            for(int j=1;j<=100;j++)
            {
                dp[i][j]=dp[i][j-1];
                if(s[i][j]=='1')
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
            }
        }
        ans=(ans+dp[5][100])%mod;
        return ;
    }
    for(int i=t;i<=5;i++)//       
    {
        swap(s[i],s[t]);
        ini(t+1);
        swap(s[i],s[t]);
    }
}
int main()
{
    //ll num=531192757;
      // ll num=531192759;
      ll num=531192758;
    while(scanf("%s",s[1]+1)!=EOF)
    {
        for(int i=2;i<=5;i++)
        scanf("%s",s[i]+1);
        ans=0;
        ini(1);
        printf("%lld
",ans*num%mod);
    }
    return 0;
}