|
|
back to boardn^2 tle? #include<bits/stdc++.h> using namespace std; int horse[510],i; long long mem[501][501]; long long count(int index,int left) { if(index==i&&left==0) return 0; if((index==i&&left>0)||(index<i&&left==0)) return 1000000; if(mem[index][left]) return mem[index][left]; int v=0,j=0,k; long long mini=1000001; for(k=index;k<i;k++) { if(horse[k]) v++; else j++; mini=min(mini,v*j+count(k+1,left-1)); } return mem[index][left]=mini; } int main() { int j,k,l; cin>>i>>j; for(k=0;k<i;k++) cin>>horse[k]; cout<<count(0,j)<<endl; return 0; } |
|
|