首页 > 代码库 > 【58测试】【贪心】【离散】【搜索】【LIS】【dp】
【58测试】【贪心】【离散】【搜索】【LIS】【dp】
第一题 大天使之剑 大意：
有n个怪，每个怪的ph 为 h[i],有三种攻击方式，普通攻击：一次打一个怪一滴血；重击（消耗1魔法值）：一次打一个怪两滴血；群体攻击（消耗1魔法值）：一次打所有怪一滴血。你有无数血，m个魔法值，每攻击一次怪后，还存活的所有怪会各攻击你一滴血。问你打完所有怪你最少被打了多少滴血。
解：
看到这道题，首先想到的是搜索，一种一种的搜，把所有情况都搜出来找最小。在草稿纸上再列一些数据就会发现，其实是个贪心。在有魔法值的时候，尽量全用于群体攻击更划算，然后没有了就普通攻击。那重击呢？由于我的数据比较特殊，所以我判重击的条件是还剩两个偶数滴血的怪，但其实，不管它的血量是偶数还是奇数，重击都更划算。还有一些杂七杂八的减没减过sum的问题等，让我调试了一个下午。看来以后静态查错很重要，少犯小错误。代码写得丑。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 100005 6 #define ll long long 7 using namespace std; 8 ll n,m,ph[maxn],ans,sum,cur=1; 9 bool jian[maxn];10 void print()11 {12 printf("%I64d",ans);13 return ;14 }15 int main()16 {17 freopen("zhijian.in","r",stdin);18 freopen("zhijian.out","w",stdout);19 cin>>n>>m;20 for (int i=1;i<=n;i++)21 scanf("%d",&ph[i]);22 sort(ph+1,ph+1+n);23 while (m)24 {25 if (n-cur+1<=2){//改用重击26 for (int i=cur;i<=n;i++)27 if (!jian[i]) ph[i]-=sum;28 while(m){29 if (cur>n) {30 print();return 0;31 }32 if (ph[cur]<=2){33 ans+=n-cur;34 cur++;continue;35 }36 ph[cur]-=2;37 ans+=n-cur+1;38 m--;39 }40 while (cur<=n){41 if (ph[cur]){42 int ci=ph[cur]-1;43 ans+=(n-cur+1)*ci;44 }45 ans+=n-cur;46 cur++;47 }48 print();49 return 0;50 }51 sum++;52 ph[cur]--;int h=cur;53 jian[cur]=true;54 ans+=n-cur+1;55 while (ph[cur]<=0){56 ans--;57 cur++;58 ph[cur]-=sum;59 jian[cur]=true;//判断 60 }61 m--;62 }63 while (cur<=n){64 if (!jian[cur]) ph[cur]-=sum;//直接减会多减 65 if (ph[cur]){66 int ci=ph[cur]-1;67 ans+=(n-cur+1)*ci;68 }69 ans+=n-cur;70 cur++;71 }72 printf("%I64d",ans);73 return 0;74 }
第二题 保卫萝卜 大意：
一个很大的矩阵，起点在正中心的方格。数据有向上下左右四个方向走的记录，输出走过的方格及所围的方格数。
解：
有两种大体思路。一个是直接正着算面积，还有反着算走不到的点。我用的后者。但有一个问题，就是存矩阵。我把它走过的地方的最左边上面下面和右边记录下来，然后在这个包含它走的所有路的方格中从0,0开始遍历dfs，到不了的地方vis=false，即为ans++。注意要在搜索范围中再加一圈，因为可能走过的路把这个范围隔开了，就搜索不到。但这是60分的做法，100分做法要用离散化坐标的思想，先放一下。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 2005 6 using namespace std; 7 const int zl[2][4]={{0,0,1,-1},{1,-1,0,0}}; 8 int n,xi,yi,idx,sum,ans; 9 bool mp[maxn][maxn],vis[maxn][maxn];10 int uup,don,le,ri,stx,sty;11 struct pp{12 int x,y;13 };14 pp tur[1005];15 char c[1005];16 void dfs(int xx,int yy)17 {18 for (int i=0;i<=3;i++)19 {20 int ki=xx+zl[0][i],kj=yy+zl[1][i];21 if (ki>=0&&kj>=0&&ki<=ri&&kj<=uup&&!vis[ki][kj]&&!mp[ki][kj])22 {23 vis[ki][kj]=true;24 sum++;dfs(ki,kj);25 }26 }27 }28 int main()29 {30 freopen("luobo.in","r",stdin);31 freopen("luobo.out","w",stdout);32 cin>>n;33 getchar();34 for (int i=1;i<=n;i++)35 {36 c[i]=getchar();37 getchar();int a;38 scanf("%d",&a);39 if (c[i]==‘L‘) {stx-=a;if (stx<le) le=stx;}40 else if (c[i]==‘R‘){stx+=a;if (stx>ri) ri=stx;}41 else if (c[i]==‘U‘) {sty+=a;if (sty>uup) uup=sty;}42 else if (c[i]==‘D‘){sty-=a;if (sty<don) don=sty;}43 tur[++idx].x=stx;tur[idx].y=sty;44 getchar();45 }46 xi=-le+1;yi=-don+1;uup+=-don+2;ri+=-le+2;47 mp[xi][yi]=true;48 for (int i=1;i<=idx;i++)49 {50 tur[i].x+=-le+1;tur[i].y+=-don+1;51 int a=min(xi,tur[i].x),b=max(xi,tur[i].x),ci=min(yi,tur[i].y),d=max(yi,tur[i].y);52 for (int j=a;j<=b;j++)53 for (int k=ci;k<=d;k++)54 mp[j][k]=true;55 xi=tur[i].x;yi=tur[i].y;56 }57 dfs(0,0);58 for (int i=0;i<=ri;i++)59 for (int j=0;j<=uup;j++)60 if (!vis[i][j]) ans++;61 printf("%d",ans);62 return 0;63 }
第三题 打地鼠 大意：
（没错怎么都是游戏的名字）打地鼠，打的这个地鼠的肥胖值一定要比上一个打的大。地鼠最多出现t次，问最多能打多少地鼠。
解：
看起来是个简单的最长上升序列。但是有一个t次，所以直接扫描加一个循环t就可以了，是不影响的。然后LIS 的nlogn的算法才能过这道题。具体的解释我觉得这个博客讲的就很清楚。http://blog.csdn.net/shuangde800/article/details/7474903
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 100005 6 using namespace std; 7 int n,maxx,k,t,a[maxn],d[maxn],ans; 8 int main() 9 {10 freopen("dishu.in","r",stdin);11 freopen("dishu.out","w",stdout);12 cin>>k>>n>>maxx>>t;13 while (k--)14 {15 memset(d,0,sizeof(d));16 int idx;ans=0;17 for (int i=1;i<=n;i++)18 scanf("%d",&a[i]);19 d[1]=a[1];ans=1;20 for(int i=1;i<=t;i++)21 for (int j=1;j<=n;j++)22 {23 if (a[j]>d[ans]) d[++ans]=a[j];24 else {25 int pos=lower_bound(d+1,d+1+ans,a[j])-d;//-d not -d-1 ?26 d[pos]=a[j];27 }28 }29 printf("%d\n",ans);30 }31 return 0;32 }
好好睡一觉，明天联考加油，不要有压力。
【58测试】【贪心】【离散】【搜索】【LIS】【dp】