hdu(5119) - 스크롤 그룹 dp

제목:
현재 한 사람에게는 n명의 친구가 있는데, 그 친구마다 하나의 값이 있다. 그 친구는 매번 몇몇 친구의 값을 선택한 후에 그것들을 다른 값으로 만들 수 있다. 만약에 마지막 값과 M보다 크면 이 사람이 이긴다.
이 사람이 이길 수 있는 방법은 몇 가지가 있냐고 물었다.
아이디어:
몇 가지 방법을 구하는 문제는 모두 dp로 생각할 수 있다.pp[i][j]: 전 i의 개인적 차이나 화합은 j에게 몇 가지 방법이 있다.40인회 MLE를 직접 열기 때문에 스크롤 그룹으로 대체할 수 밖에 없습니다.
dp[i%2][j]=dp[(i-1)%2][j]+dp[(i-1)%2][j-a[i]]; 가방dp 같은 생각을 썼어요!!
그냥 넘기면 돼.(하지만 나는 1차원으로 어떻게 최적화할 수 없을까? 아니면 1차원으로 최적화할 수 있을까?...

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef __int64 ll;
typedef unsigned __int64 ULL;
#define inf 99999999
#define maxn 50
#define ps 2097151
ll dp[2][ps+10];
ll a[maxn];
int main(){
    int T;
    scanf("%d",&T);
    int jj=1;
    while(T--){
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%I64d",&a[i]);
        }
        dp[0][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=0;j<=ps;j++){
                dp[i%2][j]=dp[(i-1)%2][j]+dp[(i-1)%2][j^a[i]];
            }
        }
        ll num=0;
        for(int i=m;i<=ps;i++) num+=dp[n%2][i];
        printf("Case #%d: %I64d
",jj++,num);
    }
    return 0;
}

hdu(5119) - 스크롤 그룹 dp

좋은 웹페이지 즐겨찾기