人品爆发,哈哈哈!分析了好久的优化,终于过了!这道经典的状态压缩DP本来写的很快!但是PKU加了个case测试限制!想呀想呀!
什么优化手段都拿出来了,终于过了,不过是到现在为止,我写的最慢一个程序5407MS,不过主要不是为了做这道,是为将betsy问题优化才做
状态压缩动规的,唉!加油吧,betsy问题,确实很难用动规写!洗澡后继续研究lrj的思路,太难了!

Source Code

Problem: 1038

User: orlando22

Memory: 2084K

Time: 5407MS

Language: C++

Result: Accepted
  • Source Code
    #include <iostream>
    using namespace std;
    
    const int N=150, M=10, MAXCH=4, MAXL=59049;
    int na[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683,/*10bits*/ 59049};
    int n, m, k;
    int dp[MAXCH][MAXL], l[MAXL];
    bool ll[MAXL];//backtrack to top
    char p[N][M];//max for index, just require three lines
    char v[N*M][N*M], bits[MAXL][M];
    #define TbaseGet(value, n) ((value/na[n])%3)
    
    //declaration
    bool valid(int x1, int y1, int x2, int y2);
    
    //implementation:optimzation, do we need to calculate for each time of validation?
    inline bool valid(int x1, int y1, int x2, int y2){
        if(x1<0||y1<0) return false;
        for(int i=x1; i<x2+1; i++){
            for(int j=y1; j<y2+1; j++)
                if(p[i][j]!=0) return false;
        }
        return true;
    }
    
    int main()
    {
        //bits records instead of macro function, save about 7 seconds, OK
        for(int i=MAXL-1; i>-1; i--){
            for(int j=0; j<M; j++)
                bits[i][j]=TbaseGet(i, j);
        }
        //for P's calculatation
        for(int i=MAXL; i>-1; i--){//Save 0.5 seconds
            l[i]=i, ll[i]=true;//default
            int start=0;
            while(start+2<10){
                if(bits[i][start]==2&&bits[i][start+1]==0&&bits[i][start+2]>0) break;
                start++;
            }
            if(start+2<10){
                int cp=i+na[start+1];
                while(!ll[cp]) cp=l[cp];//backtrack to bottom
                l[i]=cp, ll[i]=false;
            }
        }
    
        //implementation
        int c, x, y;
        cin>>c;
        while(c-->0){
            cin>>n, cin>>m, cin>>k;
            memset((void*)&p[0][0], 0, M*N);
            for(int i=0; i<k; i++){
                cin>>x, cin>>y;
                p[x-1][y-1]=1;
            }
            memset((void*)&dp[0][0], 0, sizeof(int)*MAXCH*MAXL);
            if(n==1) {cout<<0<<endl; continue;}
            int index=0;
            for(int a=1; a<n; a++){
                for(int b=0; b<m; b++,index++){
                    //blank is stable for all kind of pt
                    int x1=na[b]*2+na[b-1]*2, x2=na[b]+na[b-1]+na[b-2];
                    //replace splits to running array
                    bool v1=valid(a-2,b-1, a, b), v2=valid(a-1, b-2, a, b);//avoid circle testing,yeah! 3 seconds saving
                    for(int pt=na[m]-1; pt>=0; pt--){//replace with backtrack
                        int tmp=0;
                        if(!ll[pt]) continue;
                        if(bits[pt][b]!=0)
                            tmp=dp[(index-1+MAXCH)%MAXCH][ l[pt-na[b]] ];//A(x, y, p)=A(x, y-1, p-3^y)
                        else{
                            tmp=dp[(index-1+MAXCH)%MAXCH][ l[pt] ];//A(x, y, p)=A(x, y-1, p)
                            if(b>0&&bits[pt][b-1]==0&&v1){//!v[(a-2)*m+(b-1)][a*m+b]
                                int a1=dp[(index-2+MAXCH)%MAXCH][ l[pt+x1] ]+1;
                                if(tmp<a1)tmp=a1;//A(x, y, p)=A(x, y-2, p+(22))+1
                            }
                            //or
                            if(b>1&&bits[pt][b-2]==0&&bits[pt][b-1]==0&&v2){//!v[(a-1)*m+(b-2)][a*m+b]
                                int a1=dp[(index-3+MAXCH)%MAXCH][ l[pt+x2] ]+1;
                                if(tmp<a1)tmp=a1;//A(x, y, p)=A(x, y-3, p+(111))+1
                            }
                        }
                        dp[index%MAXCH][pt]=tmp;
                    }
                }
            }
            cout<<dp[(index-1)%4][0]<<endl;
        }
    
        return 0;
    }
    
自己写的代码,太粗心了,MAXN和MAXM都什么时候写道了,俄,不过还是没过,太慢料!怎么优化呢?我要做的事情那必须过!然后才好回去做搜索!
PS:北大的那个牛人有个地方可以改下,因为滚动数组是连续的所以不用测试了,直接-value+MAXCH再取模搞定!
#include <iostream>
#include <fstream>
using namespace std;
const int N=150, M=10, MAXCH=4, MAXL=59049;
int na[11] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683,/*10bits*/ 59049};
int n, m, k;
int dp[MAXCH][MAXL];
char p[N][M];//max for index, just require three lines,注意
#define TbaseGet(value, n) ((value/na[n])%3)
//declaration
bool valid(int x1, int y1, int x2, int y2);
//implementation
inline bool valid(int x1, int y1, int x2, int y2){
    if(x1<0||y1<0) return false;
    for(int i=x1; i<x2+1; i++){
        for(int j=y1; j<y2+1; j++)
            if(p[i][j]!=0) return false;
    }
    return true;
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("bugs.in9");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //implementation
    int c, x, y;
    cin>>c;
    while(c–>0){
        cin>>n, cin>>m, cin>>k;
        memset((void*)&p[0][0], 0, M*N);
        for(int i=0; i<k; i++){
            cin>>x, cin>>y;
            p[x-1][y-1]=1;
        }
        memset((void*)&dp[0][0], 0, sizeof(int)*MAXCH*MAXL);
        if(n==1) {cout<<0<<endl; continue;}
        int index=0;
        for(int a=1; a<n; a++){
            for(int b=0; b<m; b++,index++){
                for(int pt=na[m]-1; pt>=0; pt–){
                    int tmp=0;
                    if(TbaseGet(pt, b)!=0)
                        tmp=dp[(index-1+MAXCH)%MAXCH][pt-na[b]];
                    else{
                        tmp=dp[(index-1+MAXCH)%MAXCH][pt];
                        if(b>0&&TbaseGet(pt, b-1)==0&&valid(a-2, b-1, a, b)){
                            int a1=dp[(index-2+MAXCH)%MAXCH][pt+na[b]*2+na[b-1]*2]+1;
                            if(tmp<a1)tmp=a1;
                        }
                        //or
                        if(b>1&&TbaseGet(pt, b-2)==0&&TbaseGet(pt, b-1)==0&&valid(a-1, b-2, a, b)){
                            int a1=dp[(index-3+MAXCH)%MAXCH][pt+na[b]+na[b-1]+na[b-2]]+1;
                            if(tmp<a1)tmp=a1;
                        }
                    }
                    dp[index%MAXCH][pt]=tmp;
                }
            }
        }
        cout<<dp[(index-1)%4][0]<<endl;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
 
哎!自己写很简单,但CEOI2002的标程确实让人晕迷了一把!尝到了看不懂代码的痛苦!还是自己写个程序,过了算了!还达不到牛人的水平呀!
有种想找人垫背的冲动!袁牛直接说,他没做过,你小子自己看着办;彭牛呢,不晓得他有没得兴趣看下!Betsy的旅行,抓破脑袋写了自认为不错的动规,结果
大失所望,又慢且答案是错的!看来不能用cdq的方法,我还是写写lrj的实现吧!头痛中
 
#include <iostream>
#include <fstream>
//CEOI 2002 bugs solution : hints for betsy tour.
using namespace std;
const int MAXN=150, MAXM=10, NAL1=1000000;
int na[12] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147};
int n, m, k, s[NAL1]={0}, t[NAL1]={0}, u[NAL1]={0};
char p[MAXN*MAXM]={0};
//declaration
void dp(int x, int y, int pre, int cur, int incre);
bool valid(int x1, int y1, int x2, int y2);
//implementation
//让人头晕脑胀的一段代码,非常晕!但要自己写的话,我肯定不会那么痛苦的,谁来告诉我,这段代码什么意思!
void dp(int x, int y, int pre, int cur, int incre){
    //u[cur] x,0 get it! then turn to x,1, so, all of u[cur], at the beginning both pre and cur are zero P.
    if(y<m){
        //current no-slot
        dp(x, y+1, pre+2*na[y], cur, incre);//no move here!
        dp(x, y+1, pre+2*na[y], cur+na[y], incre);
        dp(x, y+1, pre+2*na[y], cur+na[y]*2, incre);
        //case 4
        if(valid(x-3, y, x-1, y+1)){//move more!
            dp(x, y+2, pre, cur+na[y]+na[y+1], incre+1);
            dp(x, y+2, pre, cur+2*na[y]+na[y+1], incre+1);
            dp(x, y+2, pre, cur+na[y]+2*na[y+1], incre+1);
            dp(x, y+2, pre, cur+2*na[y]+2*na[y+1], incre+1);//hight line move!
        }
        if(valid(x-2, y, x, y+1)){//sigh0,2
            dp(x, y+2, pre+na[y]+na[y+1], cur+na[y]*2+na[y+1]*2, incre+1);
        }
        if(valid(x-2, y, x-1, y+2)){//111,211,121,221,112,212,222,122
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]+na[y+1]+na[y+2], incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]*2+na[y+1]+na[y+2], incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]+na[y+1]*2+na[y+2], incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]*2+na[y+1]*2+na[y+2], incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]+na[y+1]+na[y+2]*2, incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]*2+na[y+1]+na[y+2]*2, incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]+na[y+1]*2+na[y+2]*2, incre+1);
            dp(x, y+3, pre+na[y]+na[y+1]+na[y+2], cur+na[y]*2+na[y+1]*2+na[y+2]*2, incre+1);
        }
        if(valid(x-1, y, x, y+2)){
            //analysis for here!
            dp(x, y+3, pre+na[y]*2+na[y+1]*2+na[y+2]*2, cur+na[y]*2+na[y+1]*2+na[y+2]*2, incre+1);
        }
    }
    else{
        if(u[cur]<s[pre]+incre)
            u[cur]=s[pre]+incre;
    }
}
bool valid(int x1, int y1, int x2, int y2){
    if(x1<0||x2<0) return false;
    for(int i=x1; i<x2+1; i++)
    for(int j=y1; j<y2+1; j++)
    if(p[i*m+j]) return false;
    return true;
}
#define fbase
int main()
{
    #ifdef fbase
    ifstream in("bugs.in1");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
    #endif
    //implementation
    int c, x, y;
    cin>>c;
    for(int j=0; j<c; j++){
        cin>>n,cin>>m,cin>>k;
        memset((void*)p, 0, MAXN*MAXM);
        for(int i=0; i<k; i++){
            cin>>x, cin>>y;
            p[(x-1)*m+y-1]=1;
        }
        memset((void*)s, 0, sizeof(int)*na[m]), memset((void*)t, 0, sizeof(int)*na[m]);
        for(int i=1; i<n; i++){
            memset((void*)u, 0, sizeof(int)*na[m]);
            dp(i, 0, 0, 0, 0);
            //u->t->s
            memcpy((void*)s, (void*)t, sizeof(int)*na[m]);//t is previous line
            memcpy((void*)t, (void*)u, sizeof(int)*na[m]);//u is current line
        }
        cout<<u[na[m]-1]<<endl;
    }
    #ifdef fbase
    in.close();
    #endif
    return 0;
}
#undef fbase
 
Advertisements