程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 5389 Zero Escape （MUT#8 dp優化）

HDU 5389 Zero Escape （MUT#8 dp優化）

編輯：關於C++

題意：

給出n個人的id，有兩個門，每個門有一個標號，我們記作a和b，現在我們要將n個人分成兩組，進入兩個門中，使得兩部分人的標號的和（迭代的求，直至變成一位數，我們姑且叫做求“和”操作~）分別等於a和b，問有多少種分法。

【思路】：比賽的時候還是學弟遞推的方程，當時是dp三維dp[i][j]k]:分別表示枚舉到第i位，A門，B門的狀態，但是一直沒想到怎麼進一步優化，卡在100n的復雜度了

賽後看了一下題解，（雖然高中生寫的題解看了好像也沒什麼卵用~~）發現其實可以用二維數組解決啊，只要計算所有讀入數組的和，和A，B門的比較一下，相等是時候進一步枚舉j,否則直接判斷和A，B門相等的情況，ans++,最後答案就是ans了，還是太弱了，加油吧！T_T!

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define eps 0.00000001
#define pi acos(-1,0)
#define pr 999983
using namespace std;
typedef long long LL;
const int MOD=258280327;
int  arr[110000]= {0};
int dp[110000][10]= {0};

inline LL read()
{
    int c=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
    return c*f;
}

LL get(LL n){return (n-1)%9+1;}

int main(){
    LL t,n,A,B;
    t=read();
    while(t--){
        LL sum=0;
        LL ans=0;
        memset(dp,0,sizeof(dp));
        memset(arr,0,sizeof(arr));
        n=read();A=read();B=read();
        for(int i=1; i<=n; ++i){ /// get the sum of arr[i]
            arr[i]=read();
            arr[i]=get(arr[i]);
            sum+=arr[i];
        }
        sum=get(sum);
        LL xx=get(A+B); /// judge the sum and xx
        if(sum==xx){
            dp[1][arr[1]]=1; /// dp[i][j]: 枚舉到第i位和為j的方案數
            for(int i=2; i<=n; ++i){
                for(int j=1; j<=9; ++j){
                    int k=j-arr[i];
                    if(k<=0) k+=9;
                    dp[i][j]=(dp[i-1][k]+dp[i-1][j])%MOD;
                }
            }
            ans=(dp[n][A]+dp[n][B])%MOD;
            printf(%lld
,ans);
        }
        else{
            if(sum==A) ans++;
            if(sum==B) ans++;
            printf(%lld
,ans%MOD);
        }
    } return 0;
}

/*
Sample Input
4
3 9 1
1 2 6
3 9 1
2 3 3
5 2 3
1 1 1 1 1
9 9 9
1 2 3 4 5 6 7 8 9
Sample Output
1
0
10
60
*/