• 树型动规,这道题目有必要说下,本菜就是太天真了,以为和九头龙一样,结果。。。还是有点不一样的,方程如下:
f[i,p]=min{f[son[i],k],f[bro[i],p-k-1]}  //当前i在树中,且和孩子,兄弟向父结点贡献p个连通分量;
        =min{f[bro[i],p]}  //这个是i这支一个连通分量都不提供!
好了,还有么?当然还有,加入son[i]和bro[i]作为独立一枝提供p个分量呢?
好,这就是在main里面的for i=1 to n的作用了,到这里这道题目就算完工!
当然还有另外一个转为0-1背包的版本,不过超时了,没过,一起贴在下面吧!
Source Code
Problem: 1947User: orlando22
Memory: 372KTime: 63MS
Language: C++Result: Accepted
  • Source Code
    #include <iostream>
    //pku 1947 1 <= N <= 150, 1 <= P <= N
    using namespace std;
    const int MAX=151;
    int son[MAX], bro[MAX];
    int roads[MAX][MAX];
    unsigned char cchilds[MAX],bros[MAX];
    int n, p, root=-1;
    
    //declaration
    void ctchilds(int i);
    int rebuild(int i, int p);
    
    //implementation
    void ctchilds(int i){//ensure i!=-1
        int t=1;
        for(int k=son[i]; k!=-1; k=bro[k]){
            ctchilds(k);
            t+=cchilds[k];
        }
        cchilds[i]=t;
    }
    int rebuild(int i, int p){//i!=-1
        if(i==-1){//invalid i
            if(p==0) return 0;
            return (INT_MAX>>2);//roads[i][p] i>=0
        }
        if(roads[i][p]!=-1) return roads[i][p];
        if(p==0){
            if(i==root) roads[i][p]=(INT_MAX>>2);
            else roads[i][p]=bros[i]+1;
            return (roads[i][p]);
        }
        int value=(INT_MAX>>2);
        if(bro[i]!=-1) value=rebuild(bro[i], p)+1;
        int psun, pbro;
        for(int k=0; k<=p-1; k++){
            if(cchilds[i]<k+1) break;
            psun=rebuild(son[i], k);
            pbro=rebuild(bro[i], p-1-k);
            if(psun+pbro<value) value=psun+pbro;
        }
        roads[i][p]=value;
        return value;
    }
    
    int main()
    {
        //implementation
        memset((void*)son, 0xff, sizeof(int)*MAX);
        memset((void*)bro, 0xff, sizeof(int)*MAX);
        memset((void*)cchilds, 0, sizeof(unsigned char)*MAX);
        memset((void*)bros, 0, sizeof(unsigned char)*MAX);
        memset((void*)&roads[0][0], 0xff, sizeof(int)*MAX*MAX);
    
        int a, b, ret=INT_MAX,tmp;
        cin>>n, cin>>p;
        for(int i=1; i<n; i++){
            cin>>a, cin>>b;
            bro[b]=son[a],son[a]=b;
            if(root==-1) root=a;
            else if(b==root) root=a;
        }
        for(int i=1; i<=n; i++){
            int j=i;
            while(bro[j]!=-1) j=bro[j], bros[i]++;
        }
        //backtrack for root and each childs
    	ctchilds(root);//我觉得这个是要加的,很多人用1直接算,我觉得不对,还有就是很明显的剪刀,不说了!
    	for(int i=1; i<=n; i++){
    		if(cchilds[i]>=p){
    			tmp=rebuild(son[i], p-1)+(i!=root?1:0);
    			if(tmp<ret) ret=tmp;
    		}
    	}
    	if(ret>n) ret=0;
    	cout<<ret<<endl;
    
          return 0;
    }
    
  • 这个我叫“心碎的小背包”,很烂的代码!TLE
Source Code
Problem: 1947User: orlando22
Memory: N/ATime: N/A
Language: C++Result: Time Limit Exceeded
  • Source Code
    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    #include <string>
    
    const int MAXEL=20;
    int b[MAXEL],d[MAXEL][MAXEL][2];//DP table
    int sun[MAXEL],bro[MAXEL];//sun-brother,st[]for forward-start array.
    
    //d[i][p] is for current tree and its brother.
    int RebuildFarn(int i, int p, int k){
        if(i==0){
            if(p==0){//k=0,1,2
                d[i][p][k]=0; return 0;
            }
            else{//p!=0
                d[i][p][k]=(INT_MAX>>2); return (INT_MAX>>2);
            }
        }
        if(p==0){//i!=0
            if(k!=1){//k==0
                d[i][p][k]=1; return 1;
            }
            else{//k==1
                d[i][p][k]=b[i]+1; return b[i]+1;
            }
        }
        int tmp=(INT_MAX>>2), b1,j, x1, x2;
        if(!k){//k==0, d[i][p][0]=Min{d[x1][j][0]+d[x2][p-j-1][1]}
            //d[i][p][0]=Min{d[x1][p][0]+1, d[x2][p][2]+1}
            x1=sun[i], x2=bro[x1];
            while(x1!=0){
                b1=RebuildFarn(x1, p, 0)+1;
                if(b1<tmp) tmp=b1;
                x1=bro[x1];
            }
            for(x1=sun[i], x2=bro[x1], j=0;j<p;j++){
                b1=RebuildFarn(x1,j,0)+RebuildFarn(x2,p-j-1,1);
                if(b1<tmp) tmp=b1;
            }
        }
        else{//shared with brother
            for(j=0;j<=p;j++){
                b1=RebuildFarn(i,j,0);
                if(bro[bro[i]]==0)
                    b1+=RebuildFarn(bro[i],p-j,0);
                else b1+=RebuildFarn(bro[i],p-j,1);
                if(b1<tmp) tmp=b1;
            }
        }
        d[i][p][k]=tmp;
        return tmp;
    }
    
    int main()
    {
        int n,k,j,i,pa,pb,root;
        scanf("%d%d", &n, &k);
        //reset for child's counting
        memset(b, 0, sizeof(int)*MAXEL);
        memset(sun, 0, sizeof(int)*MAXEL);
        memset(bro, 0, sizeof(int)*MAXEL);
        i=0;
        //how to find the root of tree,bitset<1...N> count no-out degree.
        //decide to implement!
        while(i<n-1){
    	scanf("%d%d", &pa, &pb);//pa->pb
    	if(!i) root=pa;
    	bro[pb]=sun[pa];
    	sun[pa]=pb;
            i++;
        }
        for(i=1; i<=pb; i++){//brother count
            j=bro[i];
            while(j!=0){b[i]++; j=bro[j];}
            if(sun[i]==root) root=i;
        }
    
        //start to memoization
        memset(&d[0][0][0], 0xff, sizeof(int)*MAXEL*MAXEL*2);//take care of MAXEL
        printf("%d\n", RebuildFarn(root, k, 0));
        return 0;
    }
  • 划分大理石,本来是练双向规划的,结果练成数学题了。

还要感谢这个链接[http://www.blogjava.net/zellux/archive/2007/07/30/133416.html]

Source Code

Problem: 1014

User: orlando22

Memory: 524K

Time: 0MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    //pku 1014, nk1620
    using namespace std;
    const int ST=6, MAX=120000;
    int p[ST], sum, i=1;
    bool f1[MAX], f2[MAX], ans;
    
    //declaration
    void calc(int st, int end, bool sf1);
    //implementation
    inline void calc(int st, int end, bool sf1){
        bool *f;
        if(sf1) memset((void*)f1, 0, sizeof(bool)*MAX),f=f1;
        else memset((void*)f2, 0, sizeof(bool)*MAX),f=f2;
        f[0]=true;//sum zero
        for(int i=st; i<=end; i++){
            for(int j=1; j<=p[i]; j++){//j*(i+1)
                for(int k=sum; k>=j*(i+1); k--){
                    if(!f[k]&&f[k-(i+1)])  f[k]=true;
                }
            }
        }
    }
    
    int main()
    {
        //implementation
        while(true){
            sum=0; ans=false;
            for(int i=0; i<ST; i++) cin>>p[i];
            if(p[5]>5) p[5]=4+p[5]%2;
            if(p[4]>6) p[4]=6-p[4]%2;
            if(p[3]>5) p[3]=4+p[3]%2;
            if(p[2]>5) p[2]=4+p[2]%2;
            if(p[1]>4) p[1]=4-p[1]%2;//这行很奇妙,但要得出结论和证明,不好搞哟!
            for(int i=0; i<ST; i++) sum+=p[i]*(i+1);
            if(sum==0) break;//all zero, terminate
            if(sum&0x1){
                cout<<"Collection #"<<(i++)<<":"<<endl;
                cout<<"Can't be divided."<<endl<<endl;
                continue;
            }
            sum/=2;
            calc(0, 2,true),calc(3, 5,false);//当当当!双向规划,俄,一个背包这么两当当,吓人!
            for(int i=0; i<=sum; i++){
                if(f1[i]&&f2[sum-i]){ans=true;break;}
            }
            if(ans){
                cout<<"Collection #"<<(i++)<<":"<<endl;
                cout<<"Can be divided."<<endl<<endl;
            }
            else{
                cout<<"Collection #"<<(i++)<<":"<<endl;
                cout<<"Can't be divided."<<endl<<endl;
            }
        }
        return 0;
    }
    

  • 这道题目也很水,但是由于我又不遗余力的贡献了1WA,南开上好像更多,所以还是要贴下的[区间控制要死人亚!]但pku上太水了,只求个答案
    所以这里要把南开的放在前面,我还是分析了下最终的最优值才得到最优序列的!因为四周开始的值我图方便直接置位0,结果,就悲剧了!因为这样
    有可能会把最优值后移,还有那个<-><=也是同理的!代码如下:
    User ID: orlando22 
    Problem ID: 1123
    Solution ID: 76375
    Language: GNU C++
    Result: Accepted


    [Text Mode ...] | [ColorCode Mode ...] | [Copy to clipboard]
    1. #include <iostream>
    2. //pku 1157 LITTLE SHOP OF FLOWERS
    3. using namespace std;
    4. const int MAX=101;
    5. int f,v,A[MAX][MAX]={0},d[MAX][MAX]={0},s[MAX][MAX]={0};
    6.  
    7. void print(int i, int j){
    8. if(i==0||j==0) return;
    9. if(s[i][j]==0) print(i,j-1);
    10. else{
    11. print(i-1, j-1);
    12. if(i==1){//i==1, find the minmal amount
    13. for(int k=1; k<=j; k++)
    14. if(d[1][k]==d[1][j]) j=k;
    15. }
    16. cout<<j<<" ";
    17. }
    18. }
    19.  
    20. int main()
    21. {
    22. //implementation
    23. cin>>f, cin>>v;
    24. for(int i=1; i<=f; i++){
    25. for(int j=1; j<=v; j++)
    26. cin>>A[i][j];
    27. }
    28. for(int i=1; i<=f; i++){
    29. for(int j=i; j<=v; j++){//d[i][f]
    30. int max=INT_MIN;
    31. if(d[i][j-1]>max&&j!=i) max=d[i][j-1];//i,j-1
    32. if(d[i-1][j-1]+A[i][j]>max) max=d[i-1][j-1]+A[i][j],s[i][j]=-1;//j
    33. d[i][j]=max;
    34. }
    35. }
    36. cout<<d[f][v]<<endl;
    37. print(f, v);
    38.  
    39. return 0;
    40. }
    41.  

  • Advertisements