TLE #18 #19,求调玄一关
查看原帖
TLE #18 #19,求调玄一关
947892
Khalil_Fong楼主2025/7/3 20:02
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
const int N=3010;
int a[3001];
int b[3001];
int c[3001];
int dp[3001][101][2];
inline int val(int k,int i) {
	int x;
	if(b[k]>b[i+1]) x=b[k];
	else x=b[i+1];
	int cnt=(1+i-k)*(i-k)>>1;
	return cnt*x;
}
inline int val1(int k,int i) {
	int cnt=(1+i-k)*(i-k)>>1;
	return cnt*b[k];
}
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c<='9'&&c>='0'){x=(x<<1)+(x<<3)+(c^48),c=getchar();}
	return x*f;
}
inline void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10^48);
}
signed main() {
	n=read(),k=read();
	int idx;
	for(register int i=1; i<=n; i++) {
		a[i]=read();
		if(a[i]==0) idx=i;
	}
	int o=0;
	for(register int i=idx; i<=n; i++) b[++o]=a[i];
	for(register int i=1; i<idx; i++) b[++o]=a[i];
	for(register int i=0; i<=n; i++) for(int j=0; j<=k; j++)  dp[i][j][0]=dp[i][j][1]=1e18;
	dp[1][1][1]=0;
	dp[1][0][0]=0;
	for(register int i=1; i<idx; i++) b[++o]=a[i];
	for(register int i=1;i<=n;i++) c[i]=b[i]*b[i];
	for(register int i=1; i<=n; i++) {
		for(register int j=2; j<=i&&j<=k; j++) {
			for(register int l=1; l<i; l++) {
				if(dp[i][j][1]>dp[l][j-1][1]+val(l,i-1)+c[i])
					dp[i][j][1]=dp[l][j-1][1]+val(l,i-1)+c[i];
				if(dp[i][j][0]>dp[l][j][1]+val1(l,i)) dp[i][j][0]=dp[l][j][1]+val1(l,i);
				if(j==k) {
					if(dp[i][j][1]>dp[l][j][1]+val(l,i-1)+c[i])
						dp[i][j][1]=dp[l][j][1]+val(l,i-1)+c[i];
					if(dp[i][j][0]>dp[l][j][1]+val1(l,i)) dp[i][j][0]=dp[l][j][1]+val1(l,i);
				}
			}
		}
	}
	int ans=1e18;
//	ans=min(dp[n][k][1],dp[n][k][0]);
	if(dp[n][k][0]<dp[n][k][1]) ans=dp[n][k][0];
	else ans=dp[n][k][1];
	print(ans);
}
2025/7/3 20:02
加载中...