T1 引子（水箱）
非常简单的模拟题目，错误点有两处：
1. 没有读入多位数字
2. 出现顺序和编号无关
然就是从1号水箱，开始递归，优先从箱底的水管递归下去，然后输出自身的编号。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include<bits/stdc++.h> using namespace std; const int MAXN=1003; char mp[MAXN][MAXN]; int n,m; int draw[MAXN][MAXN]; int numx1[200003],numy1[200003]; int numx2[200003],numy2[200003]; void paint(int col,int i,int j){ int x=i,y=j; while(mp[x][y]!='|')y++; while(mp[x][y]!='+')x++; while(mp[i][j]!='|')j--; while(mp[i][j]!='+')i--; for(int k=i;k<=x;k++){ for(int z=j;z<=y;z++){ draw[k][z]=col; } } numx1[col]=i;numy1[col]=j; numx2[col]=x;numy2[col]=y; } int go(int x,int y,int lasty){ int flag=1; while(1){ if(flag==1){ int r=y,l=y; if(y>lasty){ while(mp[x][r]!='+'&&mp[x][r]=='-')r++; } else { while(mp[x][l]!='+'&&mp[x][l]=='-')l--; } if(y>lasty){ if(mp[x][r]=='+')y=r; } else { if(mp[x][l]=='+')y=l; } x++; flag=2; } else { while(mp[x][y]!='+'&&mp[x][y]=='|')x++; if(draw[x][y]!=0)return draw[x][y]; if(mp[x][y]=='+'){lasty=y;flag=1;if(mp[x][y+1]=='-')y++;else y--;} } } } void dfs(int id){ for(int i=numx2[id]-1;i>=numx1[id]+1;i--){ if(mp[i][numy1[id]-1]=='-'){ dfs(go(i,numy1[id]-1,numy1[id])); } if(mp[i][numy2[id]+1]=='-'){ dfs(go(i,numy2[id]+1,numy2[id])); } } printf("%d\n",id); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s",mp[i]+1); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int num=0; while(isdigit(mp[i][j])){ num=num*10+mp[i][j]-'0'; j++; } if(num!=0)paint(num,i,j-1); } } dfs(1); return 0; } |
T2 可爱精灵宝贝
一道区间dp题，考场上写挂了，最后10分钟乱搞居然也有60分，考试完调了一下，有90分实际上是数据太水了。
90分代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<bits/stdc++.h> using namespace std; const int MAXN=1005; struct node{ int a,b,t; }go[MAXN]; int n,k,m; int maxt; int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=m;i++){ scanf("%d%d%d",&go[i].a,&go[i].b,&go[i].t); maxt=max(maxt,go[i].t); } int mx=0; for(int i=1;i<=k-1;i++){ int now=0; int x=k;int ans=0; while(x!=i-1&&now<=maxt){ now++; for(int j=1;j<=m;j++){ if(go[j].a==x&&go[j].t>=now)ans+=go[j].b; } x--; } if(now){ now--; now*=2; } x=k; while(now<=maxt&&x<=n){ for(int j=1;j<=m;j++){ if(go[j].a==x&&go[j].t>=now)ans+=go[j].b; } now++; x++; } mx=max(mx,ans); } for(int i=n;i>=k;i--){ int now=0; int x=k;int ans=0; while(x!=i+1&&now<=maxt){ now++; for(int j=1;j<=m;j++){ if(go[j].a==x&&go[j].t>=now)ans+=go[j].b; } x++; } if(now){ now--; now*=2; } x=k; while(now<=maxt&&x>=1){ for(int j=1;j<=m;j++){ if(go[j].a==x&&go[j].t>=now)ans+=go[j].b; } now++; x--; } mx=max(mx,ans); } cout<<mx<<endl; return 0; } |
这里区间dp用的是记忆化搜索实现的，dfs中的参数含义如下：
| 参数名 | 参数含义 |
|---|---|
| s | 第s个精灵 |
| cur | 当前时间 |
| sum | 当前状态的分数 |
| l | 当前状态的左端点 |
| r | 当前状态的右端点 |
其中，l和r指的是按位置排序后精灵序号的左右端点，相当于离散化了坐标
对于状态，我们都有以下选择：
1. 向右走去捕获右边精灵
2. 向右走，虽然捕获不到
3. 向左走去捕获左边精灵
4. 向左走，虽然捕获不到
对于每种状态的遍历，我们就可以算出f[i][j]---选择第i到第j个精灵的最大得分（不一定捕获到了）
答案就是其中最大的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<bits/stdc++.h> using namespace std; const int MAXN=1003; int n,k,m; int f[1003][1003]; int ans; struct node{ int pos; int val; int t; }a[MAXN]; bool book[MAXN]; bool cmp(node a,node b){ return a.pos<b.pos; } void dfs(int s,int cur,int sum,int l,int r){ if(f[l][r]>=sum)return; f[l][r]=sum; if(sum>ans)ans=sum; book[s]=1; if(!book[r]&&r<=m){ if(cur+abs(a[r].pos-a[s].pos)<=a[r].t){ dfs(r,cur+abs(a[r].pos-a[s].pos),sum+a[r].val,l,r+1); } else { dfs(r,cur+abs(a[r].pos-a[s].pos),sum,l,r+1); } } if(!book[l]&&l){ if(cur+abs(a[s].pos-a[l].pos)<=a[l].t){ dfs(l,cur+abs(a[l].pos-a[s].pos),sum+a[l].val,l-1,r); } else { dfs(l,cur+abs(a[l].pos-a[s].pos),sum,l-1,r); } } book[s]=0;//注意回溯 } int main(){ scanf("%d%d%d",&n,&k,&m); for(int i=1;i<=m;i++){ int d,b,c;scanf("%d%d%d",&d,&b,&c); a[i]=(node){d,b,c}; } a[++m]=(node){k,0,1};//从k位置开始 sort(a+1,a+1+m,cmp); memset(f,-1,sizeof(f)); for(int i=1;i<=m;i++){ if(a[i].pos==k&&a[i].val==0&&a[i].t==1){ dfs(i,1,0,i-1,i+1); break; } } printf("%d",ans); return 0; } |