Good Bye 2016 D. New Year and Fireworks dp+枚举、状态总数

My Sution

题意：烟花刚开始时占用一个格子的空间，然后开始移动经过ti秒(每秒移动一个格子)，开始分裂，分裂成2半，分别向2边偏移了45度，然后运动ti秒，总共n个ti，问在这个二维平面里共有多少个格子有烟花经过过了。

dp+枚举、状态总数

由于n <= 30,ti <= 5故向各个方向最多运行150个单位，故烟花只出现在一个300*300的平面内，

故定义状态dpijk，表示在ij点是否在上一秒有k方向上的烟花

对于每个ti

每一秒跑一遍ijk，把状态转移到newdpxyk里，

然后把newdpijk 拷贝到dpijk里，并维护到答案visij里，

这个ti跑完以后要状态转移是 if(newdpijk){ dp[i][j][ (k + 1) % 8] = true; dp[i][j][ (k + 7) % 8] = true;

最好跑一边vij统计出答案

复杂度(300*300*n*t)

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 3e2 + 8;

bool dp[maxn][maxn][8], newdp[maxn][maxn][8], vis[maxn][maxn];

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
    int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

    int n, t, x = 150, y = 150, i, j, k;
    dp[x][y][0] = true;
    cin >> n;
    while(n--){
        cin >> t;
        while(t--){
            memset(newdp, false, sizeof newdp);
            for(i = 0; i < maxn; i++){
                for(j = 0; j < maxn; j++){
                    for(k = 0; k < 8; k++){ if(dp[i][j][k]){ x = i + dx[k]; y = j + dy[k]; if(x >= 0 && y >= 0 && x < maxn && y < maxn){
                                newdp[x][y][k] = true;
                            }
                        }
                    }
                }
            }
            for(i =  0; i < maxn; i++){
                for(j = 0 ; j < maxn; j++){
                    for(k =  0; k < 8; k++){
                        dp[i][j][k] = newdp[i][j][k];
                        vis[i][j] |= newdp[i][j][k];
                    }
                }
            }
        }
        memset(dp, false ,sizeof dp);
        for(i = 0; i < maxn; i++){
            for(j =  0; j < maxn; j++){
                for(k = 0; k < 8; k++){
                    if(newdp[i][j][k]){
                        dp[i][j][(k + 1) % 8] = true;
                        dp[i][j][(k + 7) % 8] = true;
                    }
                }
            }
        }
    }

    int ans = 0;
    for(i = 0; i < maxn; i++){
        for(j = 0; j < maxn; j++){
            ans += vis[i][j];
        }
    }

    cout << ans << endl;



    #ifdef LOCAL
    memset(vis, false, sizeof vis);
    memset(dp, false, sizeof dp);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx