过了,但没完全过
  • 板块P4933 大师
  • 楼主Mr_Nobody_
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/1/9 14:35
  • 上次更新2024/1/9 19:53:00
查看原帖
过了,但没完全过
1088320
Mr_Nobody_楼主2024/1/9 14:35

对着第一篇题解差不多是抄了一遍,状态转移的核心原理是想明白了,但是有几个小地方一直不太懂

#include <bits/stdc++.h>
#define N 1010
#define mod 998244353
using namespace std;

int n,v,a[N],dp[N][50000],ans = 0,p = 20000;      //dp[以第i个数字结尾][公差为k] = 数列个数

signed main(){
    cin >> n;
    for(register int i = 1;i <= n;i++) cin >> a[i];
    memset(dp,0,sizeof(dp));
    for(register int i = 1;i <= n;i++){
        ans++;
        for(register int j = i-1;j >= 1;j--){           //i从第1个数字开始,j遍历第i-1到第1个数字
            int d = a[i] - a[j] + p;
            dp[i][d] += (dp[j][d] + 1);
            dp[i][d] %= mod;
            ans += dp[j][d] + 1;
            ans %= mod;
        }
    }
    cout << ans % mod << endl;
}

有三个小细节实在是不理解,首先ans++想问一下是做什么,然后ans += dp[j][d] + 1和dp[i][d] += dp[j][d] + 1这两个+1是为了什么?如果说ans++是为了加上i这个数本身的情况的话,那ans += dp[j][d]后面为啥要+1?

2024/1/9 14:35
加载中...