vijos 1282128312841285 佳佳的魔法照片/魔法药水/魔杖/魔法阵

题目链接：

/p/1282

/p/1283

/p/1284

/p/1285

T1：佳佳的魔法照片

纯模拟，我用了两次快排，但是有个数据中k为0也就是无输出，需要注意。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>using namespace std;struct ding{int node,v;}a[50010];int n,k,e[15];inline int read(){int ef=0; char ch;while ((ch>'9')||(ch<'0')) ch=getchar();while ((ch>='0')&&(ch<='9')){ef=ef*10+ch-'0';ch=getchar();}return ef;}bool cmp(const ding&x,const ding&y){return (x.v==y.v?x.node<y.node:x.v>y.v);}bool check(){for (int i=1;i<=n-1;i++)if (a[i].v<a[i+1].v) return false;return true;}int main(){n=read(); k=read(); for (int i=1;i<=10;i++) e[i]=read();for (int i=1;i<=n;i++) {a[i].v=read();a[i].node=i;}if (!check()) sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++) a[i].v+=e[(i-1)%10+1];if (!check()) sort(a+1,a+1+n,cmp);for (int i=1;i<=k-1;i++) printf("%d ",a[i]);if (k!=0) printf("%d\n",a[k]);return 0;}

T2：佳佳的魔法药水

后来问了一些同学，发现他们大多数都是取当前价格最小的那个（因为它的价格不可能再被更新了），然后去更新可以由它合成的药水的价格（但是要保证另外一种需要的药水，在此之前也已经被选为用来更新的药水了）。然而弱弱的我并没有想到这种方法，于是乎我就打了个dfs搜索。。。

当然，完全硬来肯定是不行的，首先如果当前这瓶药水的价格已经得出了，那下次访问的时候我们就返回上次得到的最优解，在存在环的情况时，我们返回的就是这瓶药水的价格和为1的方案数。

下面是具体程序：

#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<cstdlib>using namespace std;char ch;inline int read(){int ef=0; while ((ch>'9')||(ch<'0')) ch=getchar();while ((ch>='0')&&(ch<='9')){ef=ef*10+ch-'0';ch=getchar();}return ef;}struct ding{int a,b;};int val[2000],f[2000],g[2000],n,vis[2000];vector<ding>p[2000];ding dfs(int x){if (vis[x]) return ((ding){val[x],1}); //如果有环的话if (f[x]) return ((ding){f[x],g[x]});//如果已经做过一次vis[x]=true;int sum=val[x],sum2=0;for (int i=0;i<p[x].size();i++){ding now=p[x][i];ding w1=dfs(now.a),w2=dfs(now.b);//更新if ((w1.a+w2.a)<sum){sum=w1.a+w2.a;sum2=w1.b*w2.b; } else if (w1.a+w2.a==sum) sum2+=w1.b*w2.b;}if (sum==val[x]) sum2++;f[x]=sum; g[x]=sum2;vis[x]=false;return ((ding){f[x],g[x]});}int main(){//freopen("hahain.txt","r",stdin);//freopen("hahaout.txt","w",stdout);n=read();for (int i=0;i<=n-1;i++) val[i]=read();int a1,b1,c1;while (scanf("%d%d%d",&a1,&b1,&c1)!=EOF) p[c1].push_back((ding){a1,b1});ding ans=dfs(0);printf("%d %d\n",ans.a,ans.b);return 0;}

T3：佳佳的魔杖

第一次做到这么设的动归，蛮有意义的。

我们设f[i][j]为最后一段起始点在i之前（包括i）,终结点在j之前（包括j），i>=j；

很显然f[i][j]=max(f[i-1][j],f[i][j-1](j-1>=i));就是我们并没有做出新的魔杖。

但是如果我们要做出新的魔杖呢？那么f[i][j]=f[i-1][j-1]+segma(m[now](now=i;now<=j))(segma(l[now])要在lo和hi之间)。

它的意思是什么呢？就是我们用i~j的这几段做一根新的魔杖，首先长度需要在lo和hi之间，其次，为了避免冲突，上一次的魔杖最多可能是i-1~j-1或者在这之前。

程序：

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;int n;long long l[1010],m[1010],lo,hi,f[1010][1010];int main(){long long x;scanf("%d%lld%lld",&n,&lo,&hi);for (int i=1;i<=n;i++) {scanf("%lld",&x);l[i]+=l[i-1]+x;}for (int i=1;i<=n;i++){scanf("%lld",&x);m[i]+=m[i-1]+x;}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){f[i][j]=f[i-1][j];if (j-1>=i) f[i][j]=max(f[i][j],f[i][j-1]);if ((l[j]-l[i-1]>=lo)&&(l[j]-l[i-1]<=hi)) f[i][j]=max(f[i][j],f[i-1][j-1]+m[j]-m[i-1]);}printf("%lld\n",f[n][n]); return 0;}

T4:佳佳的魔法阵

就是直接dfs再加上两个剪枝。

可行性剪枝，如果一个点的上面和下面都被访问过了但是左右还未被访问（或者左右都已访问，可上下还没有），说明左右两块区间在当前走一步之后，无法联通，直接退出。

最优性剪枝：当前的最大值已经大于更新过的答案了，那就直接退出。

程序：

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define INF 2100000000using namespace std;int node,n,m,ans,k1,k2;int h[5]={0,-1,1,0,0},l[5]={0,0,0,-1,1};pair<int,int>f[3000];bool vis[60][60];void dfs(int x,int y,int node,int sum){int now=node%(n*m/2);if (node<=n*m/2) f[now]=make_pair(x,y);else {pair<int,int>p=f[now];sum=max(sum,k1*abs(p.first-x)+k2*abs(p.second-y));if (sum>ans) return;}//cout<<x<<" "<<y<<" "<<node<<" "<<sum<<endl;if (node==n*m) {ans=min(ans,sum);return;}if ((vis[x][y-1]==vis[x][y+1])&&(vis[x-1][y]==vis[x+1][y])){bool f1=vis[x-1][y]&vis[x+1][y];bool f2=vis[x][y-1]&vis[x][y+1];if (f1!=f2) return;if (f1&f2) return;}for (int i=1;i<=4;i++)if (!vis[x+h[i]][y+l[i]]){vis[x+h[i]][y+l[i]]=true;dfs(x+h[i],y+l[i],node+1,sum);vis[x+h[i]][y+l[i]]=false;}}int main(){scanf("%d%d%d%d",&n,&m,&k1,&k2);for (int i=0;i<=m+1;i++) vis[0][i]=vis[n+1][i]=true;for (int i=0;i<=n+1;i++) vis[i][0]=vis[i][m+1]=true;for (int i=0;i<=n*m;i++) f[i]=make_pair(0,0);ans=INF;vis[1][m]=true;dfs(1,m,1,0);printf("%d\n",ans);return 0;}