hdu4906 Our happy ending, 상태 압축 DP

1200 단어 ACM - 동적 계획
제목: n개의 수열을 주고 그 중에서 몇 개의 수를 취하여 새로운 수열을 구성한다. 만약에 새로운 수열에 몇 개의 수와 k가 있다면 이것은 좋은 수열이다. 이런 수열의 개수를 물어본다.n,k<=20, a[i] <=L
상태: dp[][state]에서state의 2진법은 한 명당 (1~k), 1은 찾을 수 있고 0은 찾을 수 없음을 나타낸다.
상태 이동 방정식: dp[i][state]=sum(dp[i-1][state']);  state = 1<

#include
#include
#include
using namespace std;

typedef long long LL;
const LL mod = 1e9 + 7;
LL dp[1<<22];

int main()
{
    int t, n, k, L;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d", &n, &k, &L);
        int MIN = min(L, k);
        int SIZE = (1<=0; --j) if(dp[j]>0)
            {
                LL tmp = dp[j];
                for(int p=1; p<=MIN; ++p)
                {
                    int next=(1<mod) dp[next] -= mod;
                }

                if(kmod) dp[j] -= mod;
                }

            }
        }
        LL ans = 0;
        for(int i=0; i<=SIZE; ++i) if(i&(1<mod) ans -= mod;
        }
        printf("%I64d
", ans); } return 0; }

좋은 웹페이지 즐겨찾기