Nidz05's blog

Keeping last n rows of a matrix in C++
By Nidz05, history, 3 years ago, In English

Hello, I was wondering if there is a way of keeping last n rows of a matrix efficiently in C++, for example for DP?

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

In any language, the simplest approach is to just keep the array as [n][width] instead of [height][width], and access elements as [row % n][col] instead of [row][col].

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    vector<vector<ll>> dp;

int main()
{
    SPED;
    ll n,k,t;
    cin >> n >> k >> t;
    vector<int> a(n+1);
    fff(i,1,n)
    cin >> a[i];
    ll raz = n-k*t;
    if(raz<k)
    {
        dp = vector<vector<ll>>(n+1,vector<ll>(raz+1,-INF));
        dp[0][0]=0;
        fff(i,1,n)
        {
            fff(j,0,raz)
            {
                if(j-1>=0)
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
                if(i-t>=0)
                    dp[i][j]=max(dp[i][j],dp[i-t][j]+a[i-t+1]);
            }
        }
        cout << dp[n][raz] << "\n";
    }
    else
    {
        dp = vector<vector<ll>>(n+1,vector<ll>(k+1,-INF));
        dp[0][0]=0;
        fff(i,1,n)
        {
            fff(j,0,k)
            {
                dp[i][j]=dp[i-1][j];
                if(j-1>=0 && i-t>=0)
                    dp[i][j]=max(dp[i][j],dp[i-t][j-1]+a[i-t+1]);
            }
        }
        cout << dp[n][k] << "\n";
    }
    return 0;
}

    What if i have something like this and i want to keep last t rows of dp but i am also updating the dp like so?

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
       
      Vote: I like it +11 Vote: I do not like it

      You have, for example (less lines to keep my comment short):

      fff(i,1,n)
    fff(j,0,raz) {
        if(j-1>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
        if(i-t>=0) dp[i][j]=max(dp[i][j],dp[i-t][j]+a[i-t+1]);
    }
cout << dp[n][raz] << "\n";

      Transform it to:

      fff(i,1,n)
    fff(j,0,raz) {
        if(j-1>=0) dp[i%(t+1)][j]=max(dp[i%(t+1)][j],dp[(i-1)%(t+1)][j-1]);
        if(i-t>=0) dp[i%(t+1)][j]=max(dp[i%(t+1)][j],dp[(i-t)%(t+1)][j]+a[i-t+1]);
    }
cout << dp[n%(t+1)][raz] << "\n";

      Is it any different from what you initially asked?

      → Reply