HDOJ 5742 It's All In The Mind（数学变形）
It's All In The Mind
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1179 Accepted Submission(s): 586
Problem Description
Professor Zhang has a number sequence a1,a2,...,an. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some properties of the sequence:
1. For every i∈{1,2,...,n}, 0≤ai≤100.
2. The sequence is non-increasing, i.e. a1≥a2≥...≥an.
3. The sum of all elements in the sequence is not zero.
Professor Zhang wants to know the maximum value of a1+a2∑ni=1ai among all the possible sequences.
1. For every i∈{1,2,...,n}, 0≤ai≤100.
2. The sequence is non-increasing, i.e. a1≥a2≥...≥an.
3. The sum of all elements in the sequence is not zero.
Professor Zhang wants to know the maximum value of a1+a2∑ni=1ai among all the possible sequences.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first contains two integers n and m (2≤n≤100,0≤m≤n) -- the length of the sequence and the number of known elements.
In the next m lines, each contains two integers xi and yi (1≤xi≤n,0≤yi≤100,xi<xi+1,yi≥yi+1), indicating that axi=yi.
The first contains two integers n and m (2≤n≤100,0≤m≤n) -- the length of the sequence and the number of known elements.
In the next m lines, each contains two integers xi and yi (1≤xi≤n,0≤yi≤100,xi<xi+1,yi≥yi+1), indicating that axi=yi.
Output
For each test case, output the answer as an irreducible fraction " p/ q", where p, q are integers, q>0.
Sample Input
2 2 0 3 1 3 1
Sample Output
1/1 200/201
Author
zimpha
Source
思路：
这题的意思就是说，它是一个递减数列，然后可能会给定你几个位置的数，让你求（a1+a2）/Σai 的最大值。对表达式进行变形，其实就是1/（1+(a3+…+an)/(a1+a2)）的最大值。所以只需要a1+a2最大，a3+…+ai最小就好了。那样的话就是把给定位置之前的数都赋值成给定位置的数值，最后一个给定位置之后的全都变为0。对a1、a2是不是给定位置进行分类讨论就好，很水的一题。
代码：
#include<iostream>
using namespace std;
int a[200];
int num[200];
int gcd(int a, int b)
{
int r=a%b;
if(r==0) return b;
else return gcd(b,a%b);
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m;
int sum=0;
cin>>n>>m;
for(int i=0;i<m;i++)
{
int xi,yi;
cin>>xi>>yi;
num[i]=xi;
a[xi]=yi;
}
//后面的值都最小
if(num[0]==2)
{
for(int i=0;i<m-1;i++)//中间的
{
for(int j=num[i]+1;j<num[i+1];j++)
{
a[j]=a[num[i+1]];
}
}
for(int j=num[m-1]+1;j<=n;j++)//最后的
{
a[j]=0;
}
for(int i=3;i<num[0];i++) //3-中间
{
a[i]=a[num[0]];
}
a[1]=100;
}
else if(num[0]==1&&num[1]!=2)
{
for(int i=0;i<m-1;i++)//中间的
{
for(int j=num[i]+1;j<num[i+1];j++)
{
a[j]=a[num[i+1]];
}
}
for(int j=num[m-1]+1;j<=n;j++)//最后的
{
a[j]=0;
}
for(int i=3;i<num[0];i++) //3-中间
{
a[i]=a[num[0]];
}
a[2]=a[1];
}
else if(num[0]==1&&num[1]==2)
{
for(int i=0;i<m-1;i++)//中间的
{
for(int j=num[i]+1;j<num[i+1];j++)
{
a[j]=a[num[i+1]];
}
}
for(int j=num[m-1]+1;j<=n;j++)//最后的
{
a[j]=0;
}
for(int i=3;i<num[0];i++) //3-中间
{
a[i]=a[num[0]];
}
}
else
{
for(int i=0;i<m-1;i++)//中间的
{
for(int j=num[i]+1;j<num[i+1];j++)
{
a[j]=a[num[i+1]];
}
}
for(int j=num[m-1]+1;j<=n;j++)//最后的
{
a[j]=0;
}
for(int i=3;i<num[0];i++) //3-中间
{
a[i]=a[num[0]];
}
a[1]=a[2]=100;
}//前两个数都没有输入
for(int i=1;i<=n;i++)
{
sum=sum+a[i];
}
int ll=a[1]+a[2];
int l=gcd(ll,sum);
// cout<<ll<<" "<<sum<<" "<<l<<endl;
if(l-1==0)cout<<ll<<"/"<<sum<<endl;
else cout<<(ll/l)<<"/"<<(sum/l)<<endl;
}
} 
