社区讨论

前天abc_E WA 两个点求助QWQ

AT_abc362_e[ABC362E] Count Arithmetic Subsequences参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lyma7rci
此快照首次捕获于
2024/07/15 09:04
2 年前
此快照最后确认于
2024/07/15 10:15
2 年前
查看原帖
动态规划做法
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,a[85],dp[85][85][85];
set<ll>A,B;

signed main(){
	ios::sync_with_stdio(false);
	
	cin>>n;
	for(ll i=1;i<=n;i++)cin>>a[i];
	
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<i;j++)
			dp[2][j][i]++;
		for(ll len=3;len<=i;len++)
			for(ll k2=1;k2<i;k2++)
				for(ll k1=1;k1<k2;k1++)
					if(a[k2]-a[k1]==a[i]-a[k2])
						dp[len][k2][i]+=dp[len-1][k1][k2];
	}
	
	cout<<n<<" ";
	for(ll len=2;len<=n;len++){
		ll res=0;
		for(ll k2=1;k2<=n;k2++)
			for(ll k1=1;k1<k2;k1++)
				res+=dp[len][k1][k2];
		cout<<res<<" ";
	}
	
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...