Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
149131 | 朱悦晨 | 双色马 | C++ | 通过 | 100 | 19 MS | 264 KB | 690 | 2024-05-25 16:35:51 |
#include<bits/stdc++.h> #define dp(i,j) dp[(i)%2][j] using namespace std; int dp[505][505],b[505],N,K; int main() { cin>>N>>K; for(int i=0; i<2; i++) //马厩数要大于等于马数 for(int j=i+1; j<501; j++) dp[i][j]=1<<30; //其它均设为无穷大 for(int i=1,x; i<=N; i++){ scanf("%d",&x); b[i]=b[i-1]+x; //黑马的前缀和数组 } for(int i=1; i<=K; i++) //枚举马厩 for(int j=i; j<=N-(K-i); j++) //枚举前i个马厩放的马匹数 for(int k=i-1; k<j; k++) dp(i,j)=min(dp(i,j),dp(i-1,k)+(b[j]-b[k])*(j-k-(b[j]-b[k]))); printf("%d\n",dp(K,N)); }