acm入门基础题解一.docx

《acm入门基础题解一.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ProblemA:数字三角形#include#includeconstintmaxn=110;inta[maxn][maxn],b[maxn][maxn],n;voiddata_set(){for(inti=1;i<=n;i++){for(intj=1;j<=i;j++){scanf("%d",&a[i][j]);}}}voidsolve(){for(intj=1;j<=n;j++)b[n][j]=a[n][j];for(inti=n-1;i>=1;i--)for(intj=1;j<=i;j++){if(b[i+

2、1][j+1]>b[i+1][j])b[i][j]=b[i+1][j+1]+a[i][j];elseb[i][j]=b[i+1][j]+a[i][j];}printf("%d",b[1][1]);}intmain(){while(scanf("%d",&n)!=EOF&&n!=0){data_set();solve();}return0;}ProblemB:去北京看奥运#include#includeconstintmaxn=110;constintinf=;inta[maxn],b[maxn][maxn],

3、dp[maxn][maxn],n;voiddata_set(){for(intj=0;j

4、;if(s==0)break;scanf("%d%d",&e,&l);b[s][e]=l;}for(intj=1;j<=a[i+1];j++){for(intk=1;k<=a[i];k++){if(dp[i+1][j]>dp[i][k]+b[k][j]&&b[k][j]!=inf)dp[i+1][j]=dp[i][k]+b[k][j];}}}printf("%d",dp[n+1][1]);}intmain(void){intt;scanf("%d",&t);while(t--)data_set();}ProblemC:计算直线的交点数#inclu

5、de#includeusingnamespacestd;intmain(){intn,tmp;sets[21];s[0].insert(0);s[1].insert(0);for(inti=2;i<21;i++){for(intj=0;j::iteratorit;for(it=s[j].begin();it!=s[j].end();it++){tmp=*it+(i-j)*j;s[i].insert(tmp);}}}while(cin>>n){set::iteratori

6、t;for(it=s[n].begin();it!=s[n].end();it++){if(it!=s[n].begin())cout<<"";cout<<*it;}cout<#includeinta[][11];intmain(){inti,j,n,p,q,x,m;while(scanf("%d",&n)!=EOF){if(n==0)break;m=0;memset(a,0,sizeof(a));for(i=1;i<=n;i++){scanf("%d%d

7、",&q,&p);a[p][q]++;if(p>m)m=p;}for(i=m;i>=0;i--){for(j=0;j<11;j++){intx=a[i+1][j];if(j>0&&a[i+1][j-1]>x)x=a[i+1][j-1];if(j<10&&a[i+1][j+1]>x)x=a[i+1][j+1];a[i][j]+=x;}}printf("%d",a[0][5]);}return0;}ProblemE:地道战#include#includeconstintmaxn=110;constintinf=;

8、intn,m,a[maxn][maxn],r[maxn][maxn],d[maxn][maxn];intmi