河南省第十一届ACM大学生程序设计竞赛

nyoj-1365-山区修路

内存限制:128MB 时间限制:3000ms 特判: No
通过数:4 提交数:4 难度:3

题目描述:

SNJ位于HB省西部一片群峰耸立的高大山地，横亘于A江、B水之间，方圆数千平方公里，相传上古的神医在此搭架上山采药而得名。景区山峰均在海拔3000米以上，堪称"华中屋脊"。SNJ是以秀绿的亚高山自然风光，多样的动植物种，人与自然和谐共存为主题的森林生态区。
SNJ处于中国地势第二阶梯的东部边缘，由大巴山脉东延的余脉组成中高山地貌，区内山体高大，高低不平。 交通十分不便。
最近，HB省决定修一条从YC市通往SNJ风景区的高速公路。经过勘测分析，途中需要经过高度分别为H1，H2，……,Hn的N个山区。由于高低不平，除正常的修路开支外，每段还要多出高度差|Hi - Hi-1|*X万元的斜坡费用。Dr. Kong 决定通过填高一些区域的高度来降低总的费用。当然填高也是需要一些费用的。每填高Y单位，需要付出Y2万元费用。
你能否帮Dr. Kong做出一个规划，通过部分填高工程改造，使得总的费用降下来。

输入描述:

第一行： T 表示以下有T组测试数据（ 1≤ T ≤8 ）
对每组测试数据，   
第一行：N  X（2 ≤ N ≤100，000   1≤ X ≤100）
第二行：N个整数，分别表示N个区域的高度Hi( 1<=Hi<=100 , i=1…. n)

输出描述:

对每组测试数据，输出占一行，一个整数，即经过部分填高工程改造后的最少费用。

样例输入:

复制

1
5 2
2 3 5 1 4

样例输出:

15

提示:

来源:

河南省第十一届ACM大学生程序设计竞赛

上传者：root

　　比赛时候想到正解，没敢写，真不知道100亿的复杂度0ms，真是醉了= =

  

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f 
int f[100010][110];
int a[100010];
int main(){
    int t,n,X,m,i,j,k;
    cin>>t;
    while(t--){
        int maxh=0;
        cin>>n>>X;
        for(i=1;i<=n;++i) scanf("%d",a+i),maxh=max(maxh,a[i]);
        memset(f,inf,sizeof(f));
        for(i=a[1];i<=maxh;++i) f[1][i]=(i-a[1])*(i-a[1]);
        for(i=2;i<=n;++i){
            for(j=a[i];j<=maxh;++j){
                for(k=a[i-1];k<=maxh;++k){
                    f[i][j]=min(f[i][j],f[i-1][k]+(j-a[i])*(j-a[i])+abs(j-k)*X);
                }
            }
        }
        int ans=inf;
        for(i=1;i<=maxh;++i)ans=min(ans,f[n][i]);
        cout<<ans<<endl;
    }
    return 0;
}

1370-Attack City and Capture Territory

内存限制:128MB 时间限制:3000ms 特判: No
通过数:1 提交数:1 难度:2

题目描述:

The Three Kingdoms period was a relatively famous period in the history of China. From the Battle of Chibi (AD 211) to the reunification of China in the Western Jin Dynasty(AD 280). During the period, Cao's Wei State, Liu's Shu State, and Sun's Wu Guo's Three Kingdoms stood together. Therefore, it was called the Three Kingdoms period.

In the last years of the Eastern Han Dynasty, Dong_ Z specialized in power , the coalition forces of the world's princes crusade against each other. Among them, Liu_B and Sun_Q, who are school students, also participated in the crusade.

In AD 215 , Liu_B and Sun_Q simultaneously attacked JingZhou and directly threatened Dong Z's city. There were N firepower points on the high wall, each fire point with different s trength Xi . Liu_B and Sun_Q looked at the high walls and the strong gates, they did not attack the city traightaway. They negotiate to attack firepower point alternately. Who breaks through the last firepower point, he will win the city.

Because of limited weaponry, weapons of each side can only attack one firepower at a time. But they can control whether completely destroy this firepower point or weaken the strength of firepower point.

Liu_B has a strong think-tank. After calculation, he finds out who will attack first , who will more likely win the city .

输入描述:

The first line of the input contains one integer T, which is the number of  test cases (1<=T<=10).  Each test case specifies:

* Line 1:       N                ( 1 ≤ N ≤ 100 )

* Line 2:      X1 X2… Xn        ( 1 <= Xi<=1000    i=1…. n)

输出描述:

For each test case ,  print  “Liu_B is sure to win.” Or  “Liu_B is not sure to win.” ,  suppose Liu_B first attacks.

样例输入:

复制

3
2
1 3
2
3 3
5
1 2 3 4 5

样例输出:

Liu_B is sure to win.
Liu_B is not sure to win.
Liu_B is sure to win.

提示:

    裸nim博弈。

　　

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,n,m,i,j,k;
    cin>>t;
    while(t--){
        int ans=0;
        cin>>n;
        for(i=1;i<=n;++i){
            scanf("%d",&k);
            ans^=k;
        }
        ans?puts("Liu_B is sure to win."):puts("Liu_B is not sure to win.");
    }
    return 0;
}