SPOJ BLACKOUT DP

Guys,can anyone help me regarding this problem,i mean how to appproach this problem?
Initially,i wrote a greedy solution but that didn’t work,later found out this is a dp problem.
Any kind of explanation would be appreciated

First find the prefix sums of each row and column, Then using that find the prefix sum of the grid.

Code for prefix sums
    vector<vector<pair<int,int>>> prefix_sum(n+1, vector<pair<int,int>>(m+1, mp(0,0)));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            prefix_sum[i][j].first=prefix_sum[i-1][j].first+grid[i-1][j-1];
            prefix_sum[i][j].second=prefix_sum[i][j-1].second+grid[i-1][j-1];
        }
    }
    //prefix_sum[i][j].first is the sum of i elements in the jth column
    //prefix_sums[i][j].second is the sum of j elements in the ith row.
    vector<vector<int>> gridsum(n+1, vector<int>(m+1, 0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            gridsum[i][j]=gridsum[i-1][j-1]+prefix_sum[i][j].first + prefix_sum[i][j].second - grid[i-1][j-1];
        }
    }
//gridsum[i][j] is the sum of grid[a][b] where a<i and b<j

Then find the no. of people annoyed, and the area searched by each blackout.

How to find that
    vector<pair<int,int>> blackouts(q);
    for(auto &x: blackouts){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        //Note gridsum[a][b] = sum of grid[i][j] where i<a and j<b 
        //x.first is people annoyed
        x.first=gridsum[c][d] -gridsum[c][b-1] - gridsum[a-1][d] + gridsum[a-1][b-1];
        x.second=(d-b+1)*(c-a+1);
     //x.second is area covered
    }

Then do a dp, that finds the maximum area searched if you annoy k people.

Dp relation
    vector<int> dp(k+1, 0);
    int ans=0;
    for(const auto &x : blackouts){
        for(int i=k;i>=x.first;i--){
            //x.first is people annoyed, and x.second is area covered
            dp[i]=max(dp[i], dp[i-x.first] + x.second);
            ans=max(ans, dp[i]);
        }
    }
    cout<<ans;

The dp cannot be done from x.first to k, since the previous dp states may have used this blackout, and that would double count this blackout.

1 Like

Thankyou so much man,this might be one of the best explanations i have ever encountered