上午在打usaco月賽的銅組題，T1T2是用來秒殺的，然而T3卡了一上午，下面給出題面：

　　題意大概就是輸入一個N*N的矩陣，矩陣中元素只有0與1兩種狀態，每次操作以左上角的點為矩陣中某一矩陣的左上方頂點，將該矩陣中所有元素狀態改變（即0變為1,1變為0），求將矩陣中元素全部變為0的最小次數。

　　第一次看到樣例的時候以為就是一道的DFS或BFS的搜索題，然后果斷寫了DFS，很正常就WA了。然而其實這道題需要用到貪心。。。

　　題目中提到，一個矩陣被改變兩次之后還是原先的狀態，那既然這樣，如果將右下角的點留到最后處理的話，有很大可能會重復某次操作，所以每次操作的右下角頂點應該是從右下角開始搜索的，既然這樣，每次操作的矩陣應該怎樣選取呢？

　　因為最后要把所有的元素都變為0，那么最優解其實就是保證每次操作的右下角頂點都為1，并且保證該矩陣中所含1的個數最多。

　　那么這樣的話策略就已經有了。代碼如下：　

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<string>
 5 #include<cstring>
 6 using namespace std;
 7 int sum[11][11],n,ans=0;
 8 char a[11][11];
 9 string s[11];
10 bool f[11][11];
11 int main()
12 {
13     freopen("cowtip.in","r",stdin);
14     freopen("cowtip.out","w",stdout);
15     cin>>n;
16     for (int i=1;i<=n;i++)
17         cin>>s[i];
18     for (int i=1;i<=n;i++)
19         for (int j=0;j<n;j++)
20         {
21             a[i][j+1]=s[i][j];
22             f[i][j]=true;
23             sum[i][j+1]=sum[i-1][j+1]+sum[i][j]-sum[i-1][j]+a[i][j+1]-'0';
24         }
25     for (;;)
26     {
27         bool flag=false;
28         for (int i=1;i<=n;i++)
29         {
30             for (int j=1;j<=n;j++)
31                 if (a[i][j]=='1'){flag=true;    break;}    
32             if (flag)    break;
33         }
34         if (!flag)    break;//判斷矩陣是否全部為0
35         ans++;
36         int maxx=0,x=0,y=0;
37         for (int i=1;i<=n;i++)
38             for (int j=1;j<=n;j++)
39                 if (sum[i][j]>maxx&&a[i][j]=='1')//查找右下點狀態為1且包含狀態為1的元素的個數最多的矩陣的右下點
40                 {
41                     maxx=sum[i][j];
42                     x=i;    y=j;
43                 }
44         for (int i=1;i<=x;i++)
45         {
46             for (int j=1;j<=y;j++)
47                 {
48                     if (a[i][j]=='1')    a[i][j]='0';
49                     else    a[i][j]='1';//將所選取矩陣中所有元素的狀態改變
50                 }
51         }
52         for (int i=1;i<=n;i++)
53             for (int j=1;j<=n;j++)
54                 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]-'0';//數據改變后再求矩陣前綴和
55     }
56     cout<<ans<<endl;
57     return 0;
58 }

AC代碼

總結

以上是生活随笔為你收集整理的usaco 17.Jan 铜组T3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。