물문제 연습

지비트 필기시험 두 번째 문제(상압 dp)

제목 대의:

길이가 n(n<=15)인 숫자를 정하고 한 명당 1~9의 숫자를 정하면 지금 당신은 전체 숫자를 정렬하여 흐트러뜨릴 수 있습니다. 새로 구성된 숫자 중 몇 개의 숫자가 m의 배수입니까?(m<=50)
예를 들어 S=123, 총 6가지 배열이 있다. 12313213132321, 그 중에서 m=6의 배수는 2개: 132312이다.
sample input

123 6

sample output

2

아이디어:

전체 배열은 틀림없이 안 될 거야, 15!렉 걸려서 상압 dp부터 시작해.
dp(i, t)는 현재 상태가 i이고 나머지는 t의 방안 수를 나타낸다.
그러면 하나의 방법이 된다. 첫 번째 매거는 현재 선택한 상태, 두 번째 매거는 선택되지 않은 수 j를 현재 상태의 마지막에 삽입하여 이동한다.

dp[i ^ (1 << j)][(t * 10 + (s[j] - '0')) % m] += dp[i][t];

그러나 이 제목에는 무게를 빼는 함정이 하나 더 있다. 만약 1에 두 번 또는 여러 번 나타난다면 당신은 반복해서 계산한다. 어떻게 무게를 빼야 합니까?

제거 방법 1:

이것은 내가 인터넷에서 본 방법이다. 데이터를 정렬하고 두 개의 같은 수 A와 B에 대해 언제 중복적으로 계산합니까?A를 선택하면 B를 선택하지 않거나 B를 선택하면 A를 선택하지 않는다. 이 두 가지는 중복 계산이다.그래서 우리는 정렬 후에 작은 판단을 추가한다.

j-1은 j와 같지 않고 j-1은 j에 영향을 미치지 않는다

j-1은 j와 같다. 그러나 전에 나는 j-1을 선택했다. 이때 내가 j를 다시 선택해도 영향을 주지 않는다(4를 두 개 골라서 44를 구성하는 것도 새로운 조합이다)

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
ll dp[1 << 16][55];
char s[50];
 
int main() {
    //freopen("E:\\test_data\\in.txt","r",stdin);
    //freopen("E:\\test_data\\out1.txt","w",stdout);
    ll l, r, n, m, i, j, t;
    while (scanf("%s %lld", s, &m) != EOF) {
        n = strlen(s);
        memset(dp, 0, sizeof(dp));
        sort(s, s + n);//       
        dp[0][0] = 1;
        for (i = 0; i < (1LL << n); i++) {
            for (j = 0; j < n; j++) {
                if (!(i & (1LL << j))) {
                    if (j == 0 || s[j] != s[j - 1] || (i & (1LL << (j - 1)))) {//          
                        for (t = 0; t < m; t++) {
                            dp[i ^ (1LL << j)][(t * 10 + (s[j] - '0')) % m] += dp[i][t];
                        }
                    }
                }
            }
        }
        printf("%lld
", dp[(1 << n) - 1][0]);
    }
}

제거 방법 2:

위의 방법은 좀 생각하기 어려우니 최종 결과를 고려해 다시 생각해 보자.
만약 숫자열에서 2가 2번, 4가 3번 나왔다면 몇 가지 중복이 있었을까?정답은 (2!*3!)입니다.그래서 우리는 직접 dp 방안을 가지고 마지막에 이 수를 나누면 답이다.

#include 
#define int long long 
using namespace std;
​
const int maxn=1<<16;
int dp[maxn][50];
char s[20];
int cnt[20];
signed main(){
    while(scanf("%s",s)!=EOF){
        int n,m;
        scanf("%lld%lld",&n,&m);
        int len=strlen(s);
        memset(dp,0,sizeof(dp));
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i

옥수수밭

제목 대의:

농장주인 John은 직사각형의 새 목장을 새로 샀는데 이 목장은 M행 N열(1≤M≤12;1≤N≤12)로 나누어져 각 칸마다 정사각형의 땅이다.John은 목장의 몇 칸에 맛있는 풀을 심어 젖소들이 먹을 수 있도록 할 계획이다.
유감스럽게도 일부 토지는 상당히 척박해서 풀을 심는 데 쓸 수 없다.그리고 젖소들은 잔디밭을 독점하는 느낌을 좋아하기 때문에 John은 두 개의 인접한 땅을 선택하지 않는다. 즉, 어느 두 개의 잔디밭도 공공변이 없다는 것이다.
John은 만약 잔디의 총 덩어리 수를 고려하지 않는다면, 모두 몇 가지 재배 방안이 그가 선택할 수 있는지 알고 싶어 한다.(물론 새 목장을 완전히 황폐화하는 것도 방안)

입력 형식

첫 번째 줄: 두 개의 정수 M과 N을 공백으로 구분합니다.
두 번째부터 M+1줄: 줄마다 N개의 빈칸으로 구분된 정수를 포함하여 각 토지의 상태를 설명한다.i+1행은 i행의 토지를 묘사하는데 모든 정수가 0 또는 1이다. 1이면 이 토지가 충분히 비옥하다는 것을 의미하고 0은 이 토지가 풀을 심기에 적합하지 않다는 것을 의미한다.

출력 형식

목장 분배 총 방안의 수를 100000000의 나머지로 나누는 정수

아이디어:

줄마다 12개의 열만 있다. 즉, 모든 줄의 상태 총수는 2^12를 초과하지 않는다. 그래서 우리는 줄마다 상태를 압축하고 각 상태의 합법성을 미리 처리한다. 한 상태는 합법적이고 연속적인 두 개의 1이 없어야 한다. 그리고 줄마다 합법성은 따로 말한다.
pp(s, j)는 j행에서 상태가 s인 방안수를 나타낸다. j에서 j+1으로 이동하면 2^12의 모든 상태를 다시 누적할 수 있고 합법적이면 누적하여 j+1행을 유도할 수 있다.

#include 
#include 
#include 
#include 
#include 
#define int long long 
using namespace std;
​
const int maxn=1<<12+10;
const int mod=100000000;
int dp[20][maxn];
int mp[maxn];
int mp1[maxn];
signed main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int temp;
            scanf("%lld",&temp);
            mp[i]+=(temp<>1)&i);//          1
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j

 

ZOJ3471：Most Powerful

제목 대의:

그룹 n(1<=n<=10)을 지정하고 그 중 n개의 수가 있습니다. 예를 들어 A1, A2...An.
에너지 그룹 mp 하나 더 주기 (n, n)
두 개의 수가 서로 부딪히면 mp(i, j)의 에너지를 방출하고 i와 j 중 하나를 마음대로 남긴다.
너의 임무는 이 수의 충돌 순서를 안배해서 마지막에 얻는 에너지를 가장 크게 하는 것이다.
다중 그룹 입력 주의, 10!취할 수 없다.
sample input

2
0 4
1 0
3
0 20 1
12 0 1
1 10 0
0

sample output

4
22

아이디어:

분명히 상압이 전체 배열을 해결하는 고전적인 모형이다.
dp(s)는 상태 s가 얻을 수 있는 최대 에너지를 나타낸다.
s에 없는 원소 j를 직접 매거하고 s에 있는 원소 k와 임의로 부딪히면 마지막에 j의 최대 에너지를 남기면 ok(왜 j를 남기지? 사실 누구를 남겨도 상관없어. 마지막에 모든 상태를 검색할 거야.)

#include 
using namespace std;
​
const int maxn=1<<11;
​
int dp[maxn];
int mp[12][12];
void solve(int n){
    for(int i=0;i