网站:CSUST训练
A 小Q系列故事――�丝的逆袭 HDU 4500 一道以前就做过的题，而且当时也做出来了，就是找到一个得分最高的位置，女为正数，男为负数，与邻居性别不同则加上绝对值，否则相减。
代码： 15ms
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 using namespace std; 5 int main() 6 { 7 int a,b,c[22][22],d[22][22],max,x,y,i,j; 8 while(~scanf("%d%d",&a,&b)&&a&&b) 9 { 10 max=-10000; 11 memset(d,0,sizeof(d)); 12 memset(c,0,sizeof(c)); 13 for(i=1;i<=a;i++) 14 for(j=1;j<=b;j++) 15 scanf("%d",&c[i][j]); 16 for(i=1;i<=a;i++) 17 for(j=1;j<=b;j++) 18 { 19 d[i][j]=(c[i-1][j]+c[i+1][j]+c[i][j-1]+c[i][j+1]); //都加起来 20 if(c[i][j]>0) //同性的时候取相反数 21 d[i][j]=0-d[i][j]; 22 if(d[i][j]>max) //找到最佳位置 23 { 24 x=i; 25 y=j; 26 max=d[i][j]; 27 } 28 } 29 printf("%d %d %d ",x,y,max); 30 } 31 return 0; 32 }
B Coloring Brackets CodeForces 149D
C Multiplication Puzzle POJ 1651 DP ，有n张牌，每拿走一张，sum+拿走的牌*左边的一张*右边的一张，最后只剩下两张，求最小和。d[[i][j]表示拿走(i,j)之间牌的最小和；
代码： 0ms
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 using namespace std; 5 int a[102],dp[105][105]; 6 int inf=0x3f3f3f3f; 7 int main() 8 { 9 int n,i,j,k; 10 while(~scanf("%d",&n)) 11 { 12 for(i=1;i<=n;i++) 13 scanf("%d",&a[i]); 14 memset(dp,0,sizeof(dp)); 15 for(i=2;i<n;i++) //dp[a][b]中a,b之间数的个数 16 for(j=1;j+i<=n;j++) //从1开始 17 { 18 dp[j][j+i]=inf; //初始化为无穷大 19 for(k=j+1;k<j+i;k++) //j~j+i最后拿走的那张牌 20 dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i]+a[k]*a[j]*a[j+i]); //取最小值 21 } 22 printf("%d ",dp[1][n]); 23 } 24 }
D Ping pong POJ 3928 有n个人要两两举行乒乓球比赛，裁判必须住他们中间，技能值也必须在他们中间，求最多能举行几场比赛。求出a[i]左边小于a[i]的人数c[i],a[i]右边小于a[i]的人数d[i]，那么以a[i]为裁判能举行c[i]*(n-i-d[i])+d[i]*(i-c[i]-1);
代码： 219ms
1 #include <stdio.h> 2 #include <iostream> 3 #include <string.h> 4 using namespace std; 5 int a[20005],b[110005],c[20005],d[20005]; 6 int i,j,n; 7 void updata(int x,int num) 8 { 9 while(x<=100002) 10 { 11 b[x]+=num; 12 x+=x&(-x); 13 } 14 } 15 int getsum(int x) 16 { 17 int s=0; 18 while(x>0) 19 { 20 s+=b[x]; 21 x-=x&(-x); 22 } 23 return s; 24 } 25 int main() 26 { 27 int T; 28 __int64 sum; 29 scanf("%d",&T); 30 while(T--) 31 { 32 sum=0; 33 scanf("%d",&n); 34 for(i=1;i<=n;i++) 35 scanf("%d",&a[i]); 36 memset(b,0,sizeof(b)); 37 for(i=1;i<=n;i++)//从左边找在左边比a[i]小的个数 38 { 39 updata(a[i],1); //跟新 40 c[i]=getsum(a[i]-1); 41 } 42 memset(b,0,sizeof(b)); 43 for(i=n;i>=1;i--) //从后找在右边比a[i]小的个数 44 { 45 updata(a[i],1); 46 d[i]=getsum(a[i]-1); 47 } 48 for(i=2;i<=n-1;i++) 49 sum+=c[i]*(n-i-d[i])+d[i]*(i-c[i]-1); 50 printf("%I64d ",sum); 51 } 52 return 0; 53 }