Блог пользователя Nidz05

Keeping last n rows of a matrix in C++
Автор Nidz05, история, 19 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
19 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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].

→ Ответить
  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится 
    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?

    → Ответить
    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      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?

      → Ответить