• 今天开始进入图论和数论部分,以及动规的大量练题阶段.
  • 先把原来做错的题目过了,然后再整理图论的理论部分,
  • 动规今天准备再过至少两道与四边形加速原理相关的题目,最好能把双向规划部分整理下!
  • 好,先把原来做错的水题整理在下面:再次提醒自己不能只求难度,不求基础;再简单的题目也要精心考虑,

假如这是一个大型系统里面的构件,那一点很小的不成熟就会造成大的灾难,最好的办法就是:

1.对称的考虑问题,使用状态位来控制循环,那就要考虑到状态的恢复和设置一定是对称的;

2.用统一变量控制输出,那这个全局变量在设置的时候是否是期望的方式,要基于代码结构思考!

3.对于程序逻辑相关的东西,最好写在纸上,用脑子想的东西,很容易造成纰漏,因为

每个时刻个人可能只想到一个方面,或许点子够好,但谁也不能保证其完整性,可能只是一个测试用例的解决方案。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1226 SubString

Source Code

Problem: 1226

User: orlando22

Memory: 292K

Time: 0MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    #include <string>
    
    
    using namespace std;
    const int MAX=102;
    string str[MAX];
    char t[MAX];
    
    int main()
    {
        //implementation
        int n,m,len,i,j,k;bool all;
        cin>>n;
        while(n--){
            cin>>m;
            len=MAX+2;//minmal of string
            string strMin;
            for(i=0; i<m; i++){
                cin>>t,str[i]=t;
                if(str[i].size()<len) strMin=str[i],len=str[i].size();
            }
            //compare each string with strMin
            int iMinslen=len;len=0;//全局变量的处理,细节才是真正的功力体现
            for(k=iMinslen;k>0;k--){
                all=false;//all supposed=true,我在设置这个状态控制的时候,
               //原来是在这个循环之外,想想为什么可能是错的!
            for(j=0;j<=iMinslen-k;j++){//k is len of template string
                string b=strMin.substr(j,k);//how to implement?
                strncpy(t, b.c_str(), k),t[k]='';//赫赫,这里最好用
              //逗号表达式,表示在非多线程操作下的“原子”操作~_~
                for(char *s=t,*e=t+k-1;s<=e;s++,e--){
                    char tmp=*s;*s=*e;*e=tmp;
                }
                string rb=t;
                all=true;
                for(i=0;i<m;i++){
                    if(str[i].find(b)==string::npos
			&&str[i].find(rb)==string::npos){
                        all=false;break;
			//for both which can't find substring
                    }
                }
                if(all){len=k; break;}
            }
            if(all) break;
        }
        cout<<len<<endl;
    }

    return 0;
}
  • 参数搜索的一道题目:著名的Copying Books,<实用算法>上叫做石子分配
P173页,这道问题很多人都写了解题报告.
本菜看来,如果想做这道题目,大家最好去看看书上的表述!
算法的核心在于精妙的解决问题,复杂的不可简单,同时简单也不可复杂!
我怎么看这道题目,我可以用参数搜索的方法找到上限参数P,然后在用其来进行分配!
注意:分配参数不一定可以将书可以绝对的分配到k这个数目,
容易想到,但写代码冲动的人容易忽视
[比如原来的我,其实现在代码也容易冲动,不过我会努力写出有风格的代码].
两个关键点:1.参数搜索;2.参数确定后的处理,以及再插入!
很多人在问为什么代码是错的,可以用下面的测试用例试下,pku的讨论中有!
3
5 3
1 1 1 1 10
8 3
1 1 1 1 1 1 1 10
9 3
12 12 12 12 12 12 12 12 1000
实现: http://acm.pku.edu.cn/JudgeOnline/problem?id=1505 Copying Books
Source Code
Problem: 1505User: orlando22
Memory: 284KTime: 79MS
Language: C++Result: Accepted
  • Source Code
    #include <iostream>
    
    //PKU:1505
    typedef long long int64;
    
    using namespace std;
    const int MAX=500;
    int n,k,tot;//index of array
    char s[MAX];
    int64 book[MAX];
    
    //pku1505: each parameter is less than 10000000
    //declaration
    bool check(int64 param);
    
    //implementation
    bool check(int64 param){
        int64 tmp=0;
        int tot=1;
        for(int i=n-1; i>-1; i--){
            if(book[i]>param) return false;
            if(tmp+book[i]<=param)
                tmp+=book[i];
            else//tmp+book[i]>param
                tmp=book[i],tot++;
        }
        if(tot<=k)return true;
        return false;
    }
    
    int main()
    {
        //implementation, upper boundary
        int m,upper,low,mid;
        cin>>m;
        while(m--){
            cin>>n,cin>>k;
            low=LONG_MIN,upper=0;
            for(int i=0; i<n; i++){
                cin>>book[i];
                if(book[i]>low) low=book[i];
                upper+=book[i];
            }
            low-=1;
            while(upper-low>1){
                mid=low+((upper-low)>>1);
                if(check(mid)) upper=mid;
                else low=mid;
            }
            //backtrack for minmal of max amount
            int64 tmp=0;int tot=1;
            memset((void*)s, 0, MAX);
            for(int i=n-1; i>-1; i--){
                if(tmp+book[i]<=upper) tmp+=book[i];
                else{
                    s[i]=1;//for current ending
                    tmp=book[i],tot++;
                }
            }
            if(tot!=k){//insert from the frontier, for different groups
                int left=k-tot;
                for(int i=0; i<n&&left; i++){
                    if(s[i]==0&&i!=k-1) s[i]=1,left--;
                }
            }
            for(int i=0; i<n; i++){
                cout<<book[i];
                if(s[i]==1)cout<<" /";
                if(i!=n) cout<<" ";
            }
            cout<<endl;
        }
        return 0;
    }
  • 动规的证明和代码,我贴在下面了,注意证明的思路一定要完备[对自己说的]
Supposed that M[i][k] is the minmal of maximum pages for P[0...i] of previous k scribers.
 
// k-1=<j<i,at least one book for kth scriber, then left [0...k-2] books.
描述:M[i][k]是对于k个抄书员,0...i本书,所存在的最优的最大分配数.
对于P[0...j]书,分配个k-1个抄书员,所存在的最小的最大分配数M[j][k-1],则证明如下
设K2=M[j,k-1],K1为其他非M[j,k-1]情况的最大分配,则K2<=K1.
对于第k个人的分配而言,[K1,w(j+1,i)] vs [K2,w(j,i)]
1.若w(j,i)<=K2,则M[j,k]=M[j+1,k-1](K1,K2仍然最大)
2.若w(j,i)>K2,则Max{[K2,w(j+1,i)]}=w(j+1,i);
若w(j,i)<=K1,则Max{[K1,w(j+1,i)]}=K1,而由K1>=w(j+1,i),知道M[i,k]=w(j+1,i);
若w(j,i)>K1,则Max{[K1,w(j+1,i)]}=w(j+1,i),知道M[i,k]=w(j+1,i).
这里的动规要非常小心!这里求出的只是一个关于[i,k]的最大量而已.
对于某一个针对[i,k]的最大量=Max{M[j][k-1],w(j+1,i)}.
则最大量的最小值为:M[i,k]=Min{Max{M[j][k-1],w(j+1,i)}}.
Orlando's Notes:可以直接画出线段图比较.
 

可是有个难点,题目需要将所有的[i,k]相关决策点记录下来,注意是与[i,k]相关的决策点!
这从决策空间来看,一条与[i,k]决策相关的最优解路径是无法在递归之前预判的,
因此只有用空间换时间d[i,k]来记录相关的决策点.
[这个题目明显是稀疏状态(k-2<=j<i)的,因此用自底而上的策略比较浪费运行时间].
实现代码:[运行时间,327ms,运行时间太高,可以消去递归,但估计重复的无效循环会导致无效决策产生!]
//buffer for p[0...m]
const int MAXEL=30;
int p[MAXEL];
//solution1 : DP table
int M[MAXEL][MAXEL], w[MAXEL][MAXEL], d[MAXEL][MAXEL];
int sc[MAXEL];
void DP(int m, int k);
int MemDP(int i, int k);
//M[i][k]=Min{Max{M[j][k-1],w[j+1][i]}}, k-2<=j<i;
int MemDP(int i, int k){
    if(M[i][k]!=-1) return M[i][k];
    //k>=1
    if(k==1){//k==0 is meanless
        M[i][1]=w[0][i];
        return w[0][i];
    }
    M[i][k]=INT_MAX;
    int j,tmp;
    for(j=i-1; j>=k-2; j--){
        tmp=MemDP(j, k-1);//each strategy for w(j+1,i)
        if(w[j+1][i]>tmp){
            tmp=w[j+1][i];
        }
        if(tmp<M[i][k]){//M[j][k-1],w[j][i]
            M[i][k]=tmp;d[i][k]=j;
        }
    }
    return M[i][k];
}
void DP(int m, int k){
    //calculate w[0...m-1][0...m-1]
    int i,j;
    for(i=0; i<m; i++){//w[i][0...m-1]
        w[i][i]=p[i];
        for(j=i+1; j<m; j++)
            w[i][j]=w[i][j-1]+p[j];//w[i][i]=0;
    }
    MemDP(m-1, k);
    memset(sc, 0, sizeof(int)*MAXEL);
    for(i=k,j=d[m-1][k];i;sc[j]=1,i--,j=d[j][i]);
    for(i=0; i<m; i++){
        cout<<p[i]<<" ";
        if(sc[i]) cout<<"/ ";
    }
    cout<<endl;
}

这道题目的意义不在于它多难,而在于有两个很重要的关键点:1.在处理动态规划边界的时候,s[i][j]如何处理?本菜就是在这里犯了一个错!
2.还有一点,当你用s[i][j+1],s[i][j-1](为什么不是s[i-1][j]?想想凸性怎么分析的)来处理边界的时候,那么
s[i][j+1],s[i][j-1]已经先求出来了,OK!如何规划求值过程!因此在写这类带四边形的问题时,注意以上两点,应该是很快搞定的![15分钟
:其中5-6分钟分析动规方程,我会花3-4分钟理清边界情况,哪些能用那些不能用;然后是1分钟的思考时间,如何规划求值顺序,从优化的角度
上讲,用自底向上,还是记忆化搜索;最后一半的时间中分3-4分钟编码,最后1-2分钟我观察常量定义和方程的边界处理,1-2分钟梳理代码,变量优化]
3.单独说一点,本菜要认真反思的是,为什么我在两道以上的题目里,出现了常量定义的错误,一道是将d[x][y]变量顺序写反,一道是
写常量的时候张冠李戴,一次是偶然,两次就是必然,请认真反省自己!
代码如下:

Source Code

Problem: 1160User: orlando22
Memory: 1100KTime: 110MS
Language: C++Result: Accepted
  • Source Code
    #include <iostream>
    
    using namespace std;
    typedef unsigned long long int64;
    //pku 1160
    //the number of villages V, 1 <= V <= 300, int
    //the number of post offices P, 1 <= P <= 30, int
    //each position X it holds that 1 <= X <= 10000, long
    const int MAXV=300, MAXP=30;
    long v[MAXV+1];
    int64 d[MAXP+1][MAXV+1],w[MAXV+1][MAXV+1];
    int s[MAXP+1][MAXV+1];
    //1,2...nv, start with village 1...then end with nv...
    //DP equation: d[i,j]=Min{d[i-1,k]+w(k+1,j)}.(i-1<=k<=j-1, 1<=i<=p)
    //boundary checking: m[1,j]=w[1,j],s[1,j]=mid; m[j,j]=0, s[j,j]=j-1.(1<=j<=n)
    //sum[i][j],sum of distance of all [i,j-1]->j(i<j), all [i+1,j]->i(i>j).
    //sum[i][j+1]=sum[i][j]+dis(j,j+1)*abs(i-j+1);(i<j+1)
    //sum[i][j+1]=sum[i][j]+dis(j+1,i);(i>j+1)
    //sum[i][j+1]=0;(i==j+1)
    
    int main()
    {
        //implementation
        int nv, np, ans;
        cin>>nv, cin>>np;//, cin>>ans;
        v[0]=0;
        for(int i=1; i<nv+1; i++) cin>>v[i];
        //clr
        memset((void*)&w[0][0], 0xff, sizeof(int64)*(MAXV+1)*(MAXV+1));
        memset((void*)&s[0][0], 0xff, sizeof(int)*(MAXP+1)*(MAXV+1));
        memset((void*)&d[0][0], 0xff, sizeof(int64)*(MAXP+1)*(MAXV+1));
        //pre-calculation for all w[i][j]
        for(int i=1; i<nv+1; i++) w[i][i]=0;
        for(int i=1; i<nv+1; i++){
            for(int j=i+1; j<nv+1; j++){//[i,j]
                int mid=i+((j-i)>>1);
                int64 sum=0;
                for(int k=i; k<j+1; k++) sum+=abs(v[k]-v[mid]);
                if((j-i)&0x1){//even number
                    int64 tmp=sum+((mid-i+1)-(j-mid))*(v[mid+1]-v[mid]);
                    if(tmp<sum) mid+=1,sum=tmp;
                }
                w[i][j]=sum;
                if(i==1) d[1][j]=sum, s[1][j]=mid-2;//boundary checking
            }
        }
        for(int i=1; i<np+1; i++)
            d[i][i]=0,s[i][i]=i-1;//i>=1,i<=np
        for(int i=2; i<np+1; i++){//i==1 done
            for(int j=nv; j>i; j--){//i=j?
                //d[i,j]=Min{d[i-1,k]+w[k+1,j]} k>=i-1,k<=j-1
                int l=i-1;
                if(s[i-1][j]!=-1&&l<s[i-1][j]) l=s[i-1][j];
                int r=j-1;
                if(s[i][j+1]!=-1&&r>s[i][j+1]) r=s[i][j+1];
                d[i][j]=d[i-1][l]+w[l+1][j],s[i][j]=l;
                for(int k=l+1; k<r+1; k++){
                    int tmp=d[i-1][k]+w[k+1][j];
                    if(tmp<d[i][j]) d[i][j]=tmp,s[i][j]=k;
                }
            }
        }
        cout<<d[np][nv]<<endl;
        return 0;
    }
    

Advertisements