本文主要是介绍NOIP2014 子矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
状压dp水题。
#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;int mp[20][20];
int dp[20000][20][20];
int n,m,r,c;
int sta[20000];
int v[20000][20][20];
int vv[20000][20];
int sc;int abs(int a)
{return a>0?a:-a;
}int min(int a,int b)
{return a<b?a:b;
}int main()
{scanf("%d%d%d%d",&n,&m,&r,&c);for (int i=1;i<=n;i++)for (int t=0;t<m;t++)scanf("%d",&mp[i][t]);memset(dp,-1,sizeof(dp));memset(v,0,sizeof(v));memset(vv,0,sizeof(vv));int mm=(1<<m)-1;sc=0;for (int i=0;i<=mm;i++) //寻找可用的列的选取情况{int cnt=0;for (int t=0;t<m;t++){int x=(1<<t);if (x&i)cnt++;}if (cnt==c) //找到一种{sta[sc]=i;dp[sc][0][0]=0; //新状态下第0行选取0行的最优解为0，表示可用for (int k=1;k<=n;k++){int pre=-1;for (int j=0;j<m;j++) //记录这种情况下每行的值{int x=(1<<j);if (x&i){if (pre!=-1)vv[sc][k]+=abs(mp[k][j]-mp[k][pre]);pre=j;}}for (int t=k+1;t<=n;t++) //记录这种情况下行间的值{int ans=0;for (int j=0;j<m;j++){int x=(1<<j);if (x&i){ans+=abs(mp[t][j]-mp[k][j]);}}v[sc][k][t]=ans;}}sc++;}}int ans=99999999;for (int i=1;i<=n;i++) //对于每行结尾的{for (int t=0;t<sc;t++) //状态编号为t的{for (int k=0;k<i;k++) //跟第k行组合的{for (int j=0;j<=k&&j<r;j++) //形成的矩阵行数为j的子矩阵，获得其最优解{if (dp[t][i][j+1]==-1)dp[t][i][j+1]=dp[t][k][j]+v[t][k][i]+vv[t][i];elsedp[t][i][j+1]=min(dp[t][i][j+1],dp[t][k][j]+v[t][k][i]+vv[t][i]);if (j+1==r)ans=min(ans,dp[t][i][j+1]);}}}}printf("%d\n",ans);
}这篇关于NOIP2014 子矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
