• 断了将近3天的网络,郁闷了,手头有些生疏了!
  • 今天的目标:1,DP优化模型的总结,把这几天写的程序梳理下。2,Lucene应用:索引和搜索处理部分。3,抓脑壳改简历。
  • DP的题目列表和实现:
1,Musketeers [OI 1998/1999]:IRJ的思路,将每一个人拆为两点,只要自己与自己遇到就行了,遇到条件是Meet[i,k]&&Meet[k,j],其中i要打败k,或者k要被j打败。
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=101;
int n;
bool v[MAXN][MAXN], dp[MAXN][MAXN];
#define fbase
int main()
{
#ifdef fbase
    ifstream in("MUS1.in");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    cin>>n;
    int x, y;
    char c;//for ending of input file.
    cin.get(c);//for endl
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++)
            cin.get(c), v[i][j]=c-‘0’;
        cin.get(c);//for endl
    }
    memset((void*)dp, 0, sizeof(dp));
    //for each status, bottom to up.
    for(int len=1; len<n+1; len++){//take care of order
        for(int i=0; i<n; i++){
            if(len==1) dp[i][(i+1)%n]=true;
            else{
                y=(i+len)%n;
                for(int pl=1; pl<len; pl++){
                    x=(i+pl)%n;
                    if(dp[i][x]&&dp[x][y]&&(v[i][x]||v[y][x])){
                        dp[i][y]=true;
                        break;
                    }
                }
            }
        }
    }
    for(int i=0; i<n; i++){
        if(dp[i][i]) cout<<i+1<<endl;
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
2,DDR White,书上的方程是对的,但不可用,因为这道题比较阴的是没有预先给大小,数组不可用,所以可以用滚动数组,从前面的状态滚到后面的状态,每次只需要k-1,k的两个位即可。
动规方程:d[i,j,k]->update(d[i,cstep,k+1], d[cstep,k+1]);[前向递推,将k+1全部初始化为INT_MAX,然后更新,注意k-1为INT_MAX时,不可用]
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=5, MAXK=(1<<31)-1;
int dp[MAXN][MAXN][2];
//declaration
int dptrial(int l, int r, int k, int cstep);
int inline effort(int s, int e);
//implementation
int dptrial(int l, int r, int k, int cstep){
    int tmp, min=MAXK;
    if(dp[l][r][(k-1)&0x1]!=MAXK){
        tmp=dp[l][r][(k-1)&0x1]+effort(l, cstep);
        if(dp[cstep][r][k&0x1]>tmp) dp[cstep][r][k&0x1]=tmp;
        if(min>tmp) min=tmp;
        tmp=dp[l][r][(k-1)&0x1]+effort(r, cstep);
        if(dp[l][cstep][k&0x1]>tmp) dp[l][cstep][k&0x1]=tmp;
        if(min>tmp) min=tmp;
    }
    return min;
}
int inline effort(int s, int e){//要画下哈。
    if(s==e) return 1;
    if(s==0) return 2;
    if(((s-1+3)&0x3)+1==e||(s&0x3)+1==e) return 3;
    if(((s-1+6)&0x3)+1==e||((s-1+2)&0x3)==e) return 4;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int x, min, tmp, i;
    while(cin>>x&&x){
        i=1, min=MAXK;
        //scrolling array
        for(int l=0; l<MAXN; l++)
            for(int r=0; r<MAXN; r++) dp[l][r][0]=0, dp[l][r][1]=MAXK;
        tmp=dptrial(0, 0, i, x);
        if(min>tmp) min=tmp;
        while(cin>>x&&x){
            i++;
            for(int l=0; l<MAXN; l++)
                for(int r=0; r<MAXN; r++) dp[l][r][i&0x1]=MAXK;//scrolling start
            min=MAXK;
            for(int l=0; l<MAXN; l++)
                for(int r=0; r<MAXN; r++){
                    tmp=dptrial(l, r, i, x);
                    if(min>tmp) min=tmp;
                }
        }
        cout<<min<<endl;
    }
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
3,1390 Blocks:蛮经典的,思路巧妙,先把颜色相同的合并,然后f[i,j,k]=max{f[i,j-1,0]+(len[j]+k)^2, f[i,p,k+len[j]]+f[p+1,j-1,0]}.一步优化,把pre[1…ctid]表示为每个颜色块的前一个相同颜色块,用数组链表即可。可惜代码还是慢,不说了。

Source Code

Problem: 1390 User: orlando22
Memory: 32100K Time: 1344MS
Language: C++ Result: Accepted
  • Source Code
    #include <iostream>
    
    //pku 1390 Blocks
    using namespace std;
    
    const int MAXN=201;
    int color[MAXN], len[MAXN], dp[MAXN][MAXN][MAXN], ctid=0, pre[MAXN], first[MAXN];
    
    //declaration
    int dptrial(int i, int j, int k);
    
    //implementation
    int dptrial(int i, int j, int k){
        if(dp[i][j][k]!=-1) return dp[i][j][k];
        int tmp=INT_MIN, value1, value2;
        value1=dptrial(i, j-1, 0)+(len[j]+k)*(len[j]+k);
        if(value1>tmp) tmp=value1;
        for(int p=pre[j]; p!=0&&p>=i; p=pre[p]){
            value1=dptrial(i, p, k+len[j]), value2=dptrial(p+1, j-1, 0);
            if(value1+value2>tmp) tmp=value1+value2;
        }
        dp[i][j][k]=tmp;
        return tmp;
    }
    
    int main()
    {
        //implementation
        int ncase=1, nt, n, cpid, c;
        cin>>nt;
        for(;ncase<=nt;ncase++){
            memset((void*)color, 0, sizeof(color)), memset((void*)len, 0, sizeof(color)),
            memset((void*)pre, 0, sizeof(pre)),//each previous color of block
            memset((void*)first, 0, sizeof(first)),//for current color list
            memset((void*)dp, 0xff, sizeof(dp));
            for(int i=1; i<MAXN; i++){
                for(int j=0; j<MAXN; j++) dp[i][i-1][j]=0;
            }
            cin>>n; ctid=0, cpid=0;
            for(int i=0; i<n; i++){//color is for 1..n
                cin>>c;
                if(cpid!=c) color[++ctid]=c, len[ctid]++, cpid=c, pre[ctid]=first[c], first[c]=ctid;
                else len[ctid]++;
            }
            cout<<"Case "<<ncase<<": "<<dptrial(1, ctid, 0)<<endl;
        }
        return 0;
    }
详细分析黑书上有,不过是DP里面再用DP套了一层。代码如下:
#include <iostream>
#include <fstream>
using namespace std;
const int MAXN=51, MAXM=301, MAXT=18100;
int st[MAXM], tt[MAXM], next[MAXM], sp[MAXN], first[MAXN],
    w[MAXT][MAXM], f[MAXN][MAXT], dt[MAXT][MAXM], n, m, ans, ct;
//declaration
int toSec(int time);
void format(int time);
//implementation
int toSec(int time){
    int sec=time%100; time/=100;
    int min=time%100; time/=100;
    return (time-6)*3600+min*60+sec;
}
void format(int time){
    int tmp=time/3600;//tmp
    if(tmp+6<10) cout<<0;
    cout<<tmp+6;
    time-=tmp*3600;
    tmp=time/60;
    if(tmp<10) cout<<0;
    cout<<tmp;
    time-=tmp*60;
    if(time<10) cout<<0;
    cout<<time<<endl;
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    int t;
    cin>>n>>m;
    memset((void*)first, 0xff, sizeof(first));
    for(int i=1; i<m+1; i++){
        cin>>sp[i]>>st[i]>>t; st[i]=toSec(st[i]);
        tt[i]=st[i]+t;
        next[i]=first[sp[i]];
        first[sp[i]]=i;
    }
    memset((void*)f, 0, sizeof(f));
    f[1][0]=0;
    for(int i=2; i<n+1; i++){
        memset((void*)w, 0, sizeof(w));
        for(int t=300*(i-2); t<=600*(i-2); t++){//for each starting time of i-1 gate
            memset((void*)dt, 0, sizeof(dt));
            for(int tmp=first[i-1]; tmp!=-1; tmp=next[tmp]){
                if(t<=st[tmp]&&tt[tmp]<=t+300) w[t][0]++;
                else{
                    if(st[tmp]<=t&&0<tt[tmp]-t&&tt[tmp]-t<=300) dt[t][tt[tmp]-t]–;
                    if(st[tmp]>=t&&0<=tt[tmp]-t&&tt[tmp]-t<=300) dt[t][tt[tmp]-t]++;
                }
            }
            for(int j=1; j<MAXM; j++) w[t][j]=w[t][j-1]+dt[t][j-1];//dt
        }
        for(int t=300*(i-1); t<=600*(i-1); t++){
            for(int tk=300; tk<=600; tk++){
                if(t-tk>=0) f[i][t]=max(f[i][t], f[i-1][t-tk]+w[t-tk][tk-300]);
                else break;
            }
        }
    }
    ans=-1, ct=-1;
    for(int i=300*n; i<=600*n; i++){
        if(f[n][i]>ans) ans=f[n][i], ct=i;
    }
    cout<<ans<<endl;
    format(ct);
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
时间转化有点麻烦,其他的处理一般
5,Building Game[NOI 97]:这道题目也是很经典的,前向递推和后向递推不对称。
算法分析:LRJ分析如下,由于第k堆的编号大于第k+1堆编号,不是很自然,所以等价的反一下。状态i为当前的柱子数,a为当前最大的已用积木编号,b为当前最顶层的积木编号,k是当前最顶层的积木顶面编号[0,1,2].但状态要有所选择,(i,a,b,k)若是当前已经获得柱子总长度,那么我们只有用前向动规打表到最后的(m,n,1…n,0,1,2)然后再做一次O(N^2)的比较。确实很烦,而且动规方程不好写。
而后向动规,则表示(i,a,b,k)是当前还能获得积木高度,前面一个枚举k,即可。而且动规方程可以顺利写出:
d(i, a, b, k)=
1,若新起一堆,则d(i+1,a+1, a+1, k’)+height(a+1, k’).[注意i<m==>i+1<=m]
2,若在当前堆上加一个,则d(i, a+1, a+1, k’),注意k’面一定要被k面包含
3,弃用,则d(i, a+1, b, k)。没有条件控制。
还是可能存在稀疏状态,因为有一个面包含问题,所以,用记忆化搜索如下:
#include <iostream>
#include <fstream>
using namespace std;
const int MAXM=101, MAXN=101, MAXK=3;
int d[MAXM][MAXN][MAXN][MAXK], n, m;
typedef struct Stick{
    int a, b, c;
}Stick;
Stick st[MAXN];
//declaration
int dptrial(int i, int a, int b, int k);
int inline height(int k, int id);
bool inline cover(int id1, int k1, int id2, int k2);
//implementation
int dptrial(int i, int a, int b, int k){
    if(d[i][a][b][k]!=-1) return d[i][a][b][k];
    if(a==n){d[i][a][b][k]=0; return 0;}
    //split
    int tmp=INT_MIN, c;
    if(i<m){//add another stick sepearately情况1
        for(int kl=0; kl<MAXK; kl++){
            c=dptrial(i+1, a+1, a+1, kl)+height(kl, a+1);
            if(c>tmp) tmp=c;
        }
    }
    for(int kl=0; kl<MAXK; kl++){//compare the size情况2
        if(cover(b, k, a+1, kl)){
            c=dptrial(i, a+1, a+1, kl)+height(kl, a+1);
            if(c>tmp) tmp=c;
        }
    }
    c=dptrial(i, a+1, b, k);//情况3
    if(c>tmp) tmp=c;
    d[i][a][b][k]=tmp;
    return tmp;
}
int inline height(int k, int id){
    if(k==0) return st[id].c;
    if(k==1) return st[id].b;
    if(k==2) return st[id].a;
}
bool inline cover(int id1, int k1, int id2, int k2){//id1 is under id2注意面要包含
    if(k1==0){//a,b
        if(k2==0)
            return (st[id1].a>=st[id2].a&&st[id1].b>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].b>=st[id2].a);
        if(k2==1)
            return (st[id1].a>=st[id2].a&&st[id1].b>=st[id2].c)||(st[id1].a>=st[id2].c&&st[id1].b>=st[id2].a);
        if(k2==2)
            return (st[id1].a>=st[id2].c&&st[id1].b>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].b>=st[id2].c);
    }
    if(k1==1){//a,c
        if(k2==0)
            return (st[id1].a>=st[id2].a&&st[id1].c>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].c>=st[id2].a);
        if(k2==1)
            return (st[id1].a>=st[id2].a&&st[id1].c>=st[id2].c)||(st[id1].a>=st[id2].c&&st[id1].c>=st[id2].a);
        if(k2==2)
            return (st[id1].a>=st[id2].c&&st[id1].c>=st[id2].b)||(st[id1].a>=st[id2].b&&st[id1].c>=st[id2].c);
    }
    if(k1==2){//c, b
        if(k2==0)
            return (st[id1].c>=st[id2].a&&st[id1].b>=st[id2].b)||(st[id1].c>=st[id2].b&&st[id1].b>=st[id2].a);
        if(k2==1)
            return (st[id1].c>=st[id2].a&&st[id1].b>=st[id2].c)||(st[id1].c>=st[id2].c&&st[id1].b>=st[id2].a);
        if(k2==2)
            return (st[id1].c>=st[id2].c&&st[id1].b>=st[id2].b)||(st[id1].c>=st[id2].b&&st[id1].b>=st[id2].c);
    }
}
#define fbase
int main()
{
#ifdef fbase
    ifstream in("input.txt");
    if(!in) return EXIT_FAILURE;
    cin.rdbuf(in.rdbuf());
#endif
    //implementation
    memset((void*)d, 0xff, sizeof(d));
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>st[i].a>>st[i].b>>st[i].c;
    int max=INT_MIN, tmp;
    for(int i=0; i<MAXK; i++){
        tmp=dptrial(1, 1, 1, i)+height(i, 1);//高度加和问题
        if(tmp>max) max=tmp;
    }
    cout<<max<<endl;
#ifdef fbase
    in.close();
#endif
    return 0;
}
#undef fbase
  • DP的优化模型总结:
  • 一道很有趣的面试题目,网易有道的一道题目。
打印如下形式的矩阵;
n=5:
1  2  9  10 25
4  3  8  11 24
5  6  7  12 23
16 15 14 13 22
17 18 19 20 21
手画还可以但是要编码,似乎不是很好搞。
在纸上画了下,发现路径有如下规律:只看增量,x,y坐标的变化
(0,0)//不符合就手动写了
(0,1)->(1,0)->(0,-1) l=1
(1,0)->(0,1)->(0,1)->(-1,0)->(-1,0) l=2
(0,1)->(1,0)->(1,0)->(1,0)->(0,-1)->(0,-1)->(0,-1) l=3
原来是这样的,从(0,0)开始,以(dx=0,dy=1)为起始增量,设置一个开始点,然后交换之走一个l长,再恢复并将1变为-1,走一个l长。
代码很简练,只是写的时候忘记l++了,还是写到for里面去吧。只是怎么去掉那个打表项,好像可以用console的输入处理来做,win32里面倒有API。
#include <stdlib.h>
#include <iostream>
using namespace std;
const int MAXN=10;
int a[MAXN][MAXN], n=10;
int _tmain(int argc, _TCHAR* argv[])
{
 int x=0, y=0, l=1, dx=0, dy=1, c=1;
 a[0][0]=c++;
 for(;c<=n*n;swap(dx, dy), l++){
  a[x=x+dx][y=y+dy]=c++;
  for(int i=0; i<l; i++) a[x=x+dy][y=y+dx]=c++;
  for(int i=0; i<l; i++){
   if(dx==0) a[x=x+dx][y=y-dy]=c++;
   if(dy==0) a[x=x-dx][y=y+dy]=c++;
  }
 }
 for(int i=0; i<n; i++){
  for(int j=0; j<n; j++) cout<<a[i][j]<<" ";
  cout<<endl;
 }
 system("pause");
 return 0;
}

Advertisements