动态规划做法

提交记录

#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;
}