Strange Game On Matrix

題意：給出n*m的0 1矩陣，在每一列第一個1后面找k-1個數(shù)相加，可以將1修改為0，求和的最大值并且修改的最少次數(shù)

思路：暴力過去n^3，或者求列的前綴n^2

AC代碼：

#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl ("\n") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const int N=1e5+100;int M[105][105],n,m,k,ans,mi; int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m>>k;for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){cin>>M[i][j];}}for(int j=1; j<=m; ++j){int x=0, v=0, q=0;for(int i=1; i<=n; ++i){if(M[i][j]==1){int u=0;for(int t=i; t<=n && t<i+k; ++t){if(M[t][j]==1) u++;}if(u>x){x=u, q=v;}v++;}}ans+=x, mi+=q;}cout<<ans<<" "<<mi<<endl;return 0; }

?

轉載于:https://www.cnblogs.com/max88888888/p/7666363.html

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 30 C的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。