青岛区域赛 - HZH's Blog - 自闭症
青岛区域赛
从未预料到,满怀信心出征,志在第一的我们会打银归来。
偶然中的必然,没有经过训练,没有分工的我们是如此可笑。
反省一下自己继续努力吧。
A 可以将胜负性DP变为最优解DP,将[tex]n^4[/tex]的DP转化为[tex]n^3[/tex]。
#include<bits/stdc++.h> using namespace std; int T,a1,a2,b1,b2,a11,a12,a21,a22,b11,b12,b21,b22; int f[110][110][110],g[110][110][110],t,s,i,j,k; int main(){ scanf("%d",&T); while(T--){ memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); scanf("%d%d%d%d",&a1,&a2,&b1,&b2); scanf("%d%d%d%d",&a11,&a12,&a21,&a22); scanf("%d%d%d%d",&b11,&b12,&b21,&b22); for(i=0;i<=a1;i++) for(j=0;j<=a2;j++) for(k=0;k<=b1;k++){ if(i==0&&j==0){ f[i][j][k]=(k==0); g[i][j][k]=(k==0); continue; } g[i][j][k]=b2+1; if(i){ if(k)g[i][j][k]=min(g[i][j][k],f[max(i-b11*(k!=0),0)][j][k]); g[i][j][k]=min(g[i][j][k],max(f[max(i-b11*(k!=0)-b21,0)][j][k],1)); if(j)g[i][j][k]=min(g[i][j][k],max(f[max(i-b11*(k!=0),0)][max(j-b22,0)][k],1)); } if(j){ if(k)g[i][j][k]=min(g[i][j][k],f[i][max(j-b12*(k!=0),0)][k]); if(i)g[i][j][k]=min(g[i][j][k],max(f[max(i-b21,0)][max(j-b12*(k!=0),0)][k],1)); g[i][j][k]=min(g[i][j][k],max(f[i][max(j-b12*(k!=0)-b22,0)][k],1)); } f[i][j][k]=max(f[i][j][k],g[i][j][max(k-a11*(i!=0)-a21*(j!=0),0)]); if(g[i][j][max(k-a11*(i!=0),0)])f[i][j][k]=max(f[i][j][k],g[i][j][max(k-a11*(i!=0),0)]+a22*(j!=0)); if(g[i][j][max(k-a21*(j!=0),0)])f[i][j][k]=max(f[i][j][k],g[i][j][max(k-a21*(j!=0),0)]+a12*(i!=0)); if(g[i][j][k])f[i][j][k]=max(f[i][j][k],g[i][j][k]+a12*(i!=0)+a22*(j!=0)); } t=f[a1][a2][b1]>b2; s=g[a1][a2][b1]>b2; if(t&&s)puts("Alice wins");else if((!t)&&(!s))puts("Bob wins");else puts("It depends"); } }
B 签到题
C 可能是复杂度奇怪的DP,并没有想到较好的做法
D 并没有好的想法
2017年11月12日 23:53
膜银牌大佬
2018年2月04日 00:45
他高一au诶
2022年9月10日 05:41
Computer Knowledge is very much essential nowadays. Even Checking the Results of various examinations, AP SSC computer Model Paper Downloading hall tickets and study materials for multiple exams and booking tickets etc ..need minimum Technical Knowledge is much more important for everyone. Since the Government of AP also provided Computer labs for students in all Government schools also.