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

Автор ianlim224, история, 3 года назад, По-английски

I keep getting a TLE verdict for the CSES Book Shop question https://cses.fi/problemset/task/1158/ I've coded an iterative bottom-up DP:

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define pb push_back

#define all(x) x.begin(), x.end()
#define FOR(i, a) for (int i = 0; i < (a); i++)

typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef tuple<int, int, int> iii;
typedef vector<ll> vll;

const int INF = 1e9;
const ll INFL = 1e18;
const int MOD = 1000000007;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, x;
  cin >> n >> x;
  vector<vi> dp(x + 1, vi(n + 1));

  vi prices(n + 1);
  vi pages(x + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> prices[i];
  }
  
  for (int i = 1; i <= n; ++i) {
    cin >> pages[i];
  }
  
  for (int i = 1; i <= x; ++i) {
  	for (int j = 1; j <= n; ++j) {
  		if (i < prices[j]) dp[i][j] = dp[i][j &mdash; 1];
  		else dp[i][j] = max(dp[i][j &mdash; 1], pages[j] + dp[i &mdash; prices[j]][j &mdash; 1]);
  	}
  }
  cout << dp[x][n];
}

The implementation is very similar to the sample codes found on unofficial editorials. Yet I still get TLE... Can anyone help to point out the issue/how to improve on the efficiency of my code? Thanks in advance!

Теги dp, cses
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Either you make the array 1D instead of 2D by reducing the dp states (second state can be removed)

Or just swap the dimensions of the dp so you will have vector dp(n + 1, vi(x + 1)) instead of vector dp(x + 1, vi(n + 1))

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How does swapping the dimensions reduce computation time? How should I store the dp states using 1d array? Thanks

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Hey, I also faced this problem. Strangely enough, swapping the dimensions helped me to get AC. Did you figure out the reason behind swapping the dimensions ?