题意：有长度为n的数列，有m种颜色，问最少的花费，使得数列中为0的点刷上颜色，并可根据颜色把数列分为正好k段。
思路：dp，开一个dp[n][m][k]，表示前n个以m为结尾的k段最小花费，转移方程是：如果这个点非0，那么只能从n-1 转移到a[i]这一个颜色，如果是0，即没有颜色限制，那么可以从n-1个中以非m结尾的状态转移过来，即dp[n][非m][k-1] .或者是以m为结尾的状态转移，即dp[n][m][k];
//#include<bits/stdc++.h> //#include<unordered_map> //#include<unordered_set> #include<functional> #include<algorithm> #include<iostream> #include<iomanip> #include<climits> #include<cstring> #include<cstdlib> #include<cstddef> #include<cstdio> #include<memory> #include<vector> #include<cctype> #include<string> #include<cmath> #include<queue> #include<deque> #include<ctime> #include<stack> #include<map> #include<set> #define fi first #define se second #define pb push_back #define INF 0x3f3f3f3f #define pi 3.1415926535898 #define lson l,(l+r)/2,rt<<1 #define rson (l+r)/2+1,r,rt<<1|1 #define Min(a,b,c) min(a,min(b,c)) #define Max(a,b,c) max(a,max(b,c)) // #pragma GCC optimize("unroll-loops") // #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast,no-stack-protector") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") using namespace std; typedef long long ll; typedef pair<int,int> P; typedef unsigned long long ull; const int MOD=1e9+7; const ll LLMAX=2e18; const int MAXN=1e6+10; template<class T> inline void read(T &DataIn) { DataIn=0; T Flag=0; char c=getchar(); while(!isdigit(c)){ Flag|=c=='-'; c=getchar(); } while(isdigit(c)){ DataIn=DataIn*10+c-'0'; c=getchar(); } DataIn= Flag? -DataIn: DataIn; } template<class T> inline void write(T DataOut,char EndChar=' ') { T lenth=0,number[30]; if(DataOut==0){ putchar(48); return; } while(DataOut>0){ number[++lenth]=DataOut%10; DataOut/=10;} for(int i=lenth;i>=1;i--) putchar(number[i]+48); putchar(EndChar); } priority_queue<int,vector<int>,less<int> > qd; priority_queue<int,vector<int>,greater<int> > qu; ll a[200][200],origin[200],change[200]; ll dp[200][200][200]; const ll inff = 0x3f3f3f3f3f3f3f3f; //18 int main(void) { FILE *fin=NULL,*fout=NULL; ios::sync_with_stdio(false); cin.tie(0); //fin=freopen("D:/Project__C++/testdata.in","r",stdin); //fout=freopen("D:/Project__C++/testdata.out","w",stdout); int n,m,k; cin>>n>>m>>k; for(int i=1;i<=n;i++) cin>>origin[i]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) for(int t = 0; t<=k;t++) dp[i][j][t] = inff; for(int i=1; i<=m; i++)dp[0][i][0]=0ll; dp[0][1][1] = 0; //这个初始条件是看到 //1 1 1 0 5 这个样例发现的 for(int i=1; i<=n; i++){ for(int j=1; j<= m; j++){ for(int f = 1; f<=m; f++){ for(int t = 1; t<=min(i,k); t++){ //这里要去min才行。 if(origin[i] != 0){ if(origin[i]==j){ if(j==f) dp[i][j][t] = min(dp[i][j][t],dp[i-1][f][t]); else dp[i][j][t] = min(dp[i-1][f][t-1],dp[i][j][t]); } } else { if(j!=f)dp[i][j][t] = min(dp[i-1][f][t-1] + a[i][j],dp[i][j][t]); else dp[i][j][t] = min ( dp[i-1][f][t] + a[i][j],dp[i][j][t]); } // cout<<i<<" "<<j<<" "<<t<<":"; // cout<<dp[i][j][t]<<endl; } } } // cout<<endl; } ll ans=inff; for(int i=1; i<=m; i++) if(ans > dp[n][i][k]) ans = dp[n][i][k]; if(ans>=inff) ans=-1; cout<<ans<<endl; return 0; }