課程總結第四周

動態規劃:課上所講跟我原先開始預習時對于它的理解不一樣，思路和代碼實作的方法都很不一樣，所以開始時造成了一定困難，學習思考過后，才將自己的思路糾正過來，也加深了對動態規劃定義的理解，
現在看來：
1.DP的關鍵在于找到狀態轉移方程，列舉子問題的各種可能情況，再進行計算（對于金幣那題就是根據走過路徑更新各個位置上的金幣數），
2.當前每一個狀態都會影響下一個狀態的決策，并且都是根據狀態轉移方程進行的，子問題的最優值便是源問題的解，
3.子問題的結構和源問題的結構是一致的，
4.DP好像和分治法類似，然后我去稍微看了看，只是簡單了解，對于子問題重復計算引起的復雜度區別，
求解步驟：
1.將問題拆分，
2.定義問題狀態和狀態之間的關系，
3.將每個狀態最優解保留下來，為了在下一步推導時使用前一步的最優解，程序中必然舍去相比較的差解，
（這些都是理論知識，大致框架，最重要的還是分析題目）

之前我認為，一個動態問題可以分成若多個子問題，得到各個子問題的最先值，那么開始時如何規劃便顯而易見，
1.比如那個吃金幣的問題，我的思路是反正這個人都會從左上端走到右下端，那么便從右下端開始考慮問題，分析從哪里走到這金幣最多，然后用下方的金幣逐層更新上方的金幣，當更新到離起始位置只剩一格時，那么往哪里走便很明顯，起始位置便是最大金幣值，
識訓：我開始這個思路沒有問題，當然其實復雜度是一樣的，我開始的想法比較麻煩，多此一舉，此題真的沒必要逆向考慮，但還是要有這種思想，
我的思路敲出的代碼：

int a[10005][10005];
int main()
{   memset(a,0,sizeof(a));
    int m,n,s;cin>>m>>n;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    }
    for(int i=m-1;i>=0;i--)
    {
        for(int j=n-1;j>=0;j--)
        {
           a[i][j]=max(a[i+1][j],a[i][j+1])+a[i][j];
        }
    }
    cout<<a[0][0]<<endl;
    return 0;
}

課上思路：

int a[10005][10005];
int main()
{
    int m,n,s;cin>>m>>n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>s;
            a[i][j]=max(a[i-1][j],a[i][j-1])+s;
        }
    }
    cout<<a[m][n]<<endl;
    return 0;
}

2.然后是最長子序列問題，給出一個陣列序列，然后無關乎坐標，得到一個最大長度的子序列
我的思路：開始我并沒有將他當作一個動態陣列問題，而是用一種貪心思想，先找到最大位置的下標，然后往前遍歷，記錄一共多少個數比它小，然后加1，之所以取最大數，是因為這樣能保證有足夠多空間的數比他小，比如9，就會有1-8這段空間，有更大可能取得最長序列，之后我發現，9有可能在序列的前面位置，便改進了思路，n個數共取n次最小值，
然后看完課上代碼，發現大致思路相同，不同點在于不必要每次取最大數了，因為反正都要取n次，所以每次取最大值便沒了意義，便簡化了思路，代碼也更容易寫出了，
DP .T題識訓：
（此題雖不難，但我wr了4次，超時2次，提交錯誤1次，最后才ac，其實代碼都是一樣的，就是細節沒做好，所以同樣的代碼距離能夠ac有時只是一些細節的完善）
1.ios::sync_with_stdio(false); cin.tie(0);這段加快輸入的代碼我開始沒有重視，結果發現非常有效，同樣的代碼快了將近500 ms，最好放到main函式的開頭位置，
2.從子序列末尾找到子序列的開頭位置，若不同子序列有相同的結果，去掉break，便是找到第一個這樣的子序列，

 for(int i=g;i>=1;i--)
  {
    temp+=a[i];
    if(temp==maxn)
    {
      s=i;
      break;
   }

3.最長公共子序列的問題，題目：兩個字串，找出公共部分的數量，----->>>這題代碼和思路其實我都聽懂了，但總感覺差點什么，最后明白是差了分析這個問題的方式，這種方式是老師上課沒有提及的，
識訓：將整個求解程序用一個最優決策表來描述，行表示決策的階段，串列示問題狀態，表格需要填寫的資料一般對此問題在某個階段某個狀態下的最優解，填表的程序就是根據遞推關系填寫表格，而本題可制作一個二維表格，列是字串A的元素，行是字串B的元素，填寫表格，在第i行第j列下的數字便是當前最大公共字符數，

總結幾道codeforces上的題目：
一. D . Epic Transformation
大致題意：給定一個陣列，每次刪去兩個不同的輸，問這個陣列最少剩下幾個數，
我的思路：第一下就想到了要用優先佇列，每次將最大一個數pop，然后將優先佇列進行遍歷，若有一個和最大值不一樣的，便在佇列中刪去這個數；然后再取一個最大值，刪去一個不一樣的，最后可能情況：pop出的的最大值和佇列內的數一樣，或者佇列為空，但是遇到幾個問題，
1.不知道如何對優先佇列進行遍歷操作，之后了解到只能用回圈不斷的pop，和push，
2.優先佇列好像無法洗掉佇列內某個特定的元素，
識訓：最后發現這個思路其實行不通，有個樣例通不過，洗掉的一對元素是需要組合的，不能隨意洗掉兩個不同的元素，最后，只能去看別人寫的代碼，其實思路對了一半，確實要用到優先佇列，但要配合map進行使用，我照著別人的思路敲了一遍，發現自己還是不會用map，對它的一些操作還不熟，包括要使用到的迭代器，雖然沒系統學過，但這也不是理由，簡單了解下來已經大致會用，算學到了，

int main()
{
    int t;cin>>t;
    while(t--)
    {
        int m,n;cin>>n;
        map<int,int>cnt;
        for(int i=0;i<n;i++)
        {
            cin>>m;cnt[m]++;   //以陣列形式對map進行存盤，first是這個值，second是這個數出現的次數
        }
        priority_queue<int> q;
        map<int,int>::iterator it;    //學到的迭代器，和指標好像類似
        for(it=cnt.begin();it!=cnt.end();it++)
        {
            int r=it->second;
            q.push(r);             //將second存入優先佇列q；
        }
        int ans=0;
        while(q.size()>=2)
        {
            int a=q.top();q.pop(); 
            int b=q.top();q.pop();
            ans+=2;
            a--;b--;            //每次取出出現次數最多的數進行消除
            if(a) q.push(a);   
            if(b) q.push(b);    //再次存入
        }
        cout<<n-ans<<endl;
    }
    return 0;
}

然后我又發現了一個更好，更精妙的方法，既不要用到priority_queue也不要用map，直接找出消除數字的規律來，只要用組回圈便可解決問題，但這個方法巧妙，便意味著很難想到，事情就是這樣，想省力就要找到多花心思；不想探究更多，便要多出力，
思路：將陣列升序排列，將第一個數，和比它大（n/2+1）的數進行組合消除，非常巧妙，雖然我也不知道什么原理，但就是能ac，

int a[200005];
int main()
{
    int t;cin>>t;
    while(t--)
    {
       int n;cin>>n;
       for(int i=0;i<n;i++)
       {
           cin>>a[i];
       }
       sort(a,a+n);int num=n;
       for(int i=0;i<n/2;i++)
       {
           if(a[i]!=a[(n+1)/2+i]) num-=2;
       }
       cout<<num<<endl;
    }
    return 0;
}

二 .A. GCD Sum
這題是div.2的第一題，所以我是ac的，便大致總結一下：就是將一個數和它各個位上數的和取最大公約數，不為1即可，可進行遞增，我用了兩個普通函式，一個求各個位上的和，一個求最大公約數（當時想到可用遞回來加快運行速度，雖然不是很理解，但也能大體寫出）
識訓：最大公約數的遞回，便當做學習遞回的起點，開始吧，

int gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);   // 最大公約數的遞回
}

三.B. Box Fitting
第二題，這題一直困擾了我很久，
大致題意：往一個大箱子里裝盒子，盒子高度都為1，長度不等，給定大箱子的的長度w，問最多需要裝幾層---->>>我看出這是個貪心的問題，第一個想法是覺得這題和那個裝包裹的題很像，凡是大于w/2長度的高度累加1，剩下的空間放那些小的，將小的排好序，慢慢放進去，但是這樣做很麻煩，----->>>于是想到先將這些小箱子降序排列，先放一個大的，再從末尾挑小的放進去，直到放不下為止，然后高度+1，再放一個大的，重復此操作，這樣思路更清晰，代碼也更好寫，---->>>然后又發現了一個特別好的方法，又是要用到優先佇列，先將陣列從大到小排好序，將（w-陣列末尾元素值），也就是剩余空間，放入優先佇列，不斷的放和更新，直到出現一個陣列元素大于這個剩余空間，高度累加1，很精妙！！

以上這就是本周的感悟和識訓，雖然本周沒有要求寫總結，但我還是寫了4000多字，也算是警醒自己：有些事情有時，需要一個理由；而有些事情，僅僅是因為想做，