September 15th, 2018 acm learning log

2018.9.15 ACM-ICPC 2018 Jiaozuo District Network Preliminaries

A.Magic Mirror (over)

Sign up to convert the input string to uppercase Then compare with the given string

B.Mathematical Curse (over)

题意: Given the original integer K, given a non-zero integer string of length N, then give M calculations Symbol, the maximum result after using M operators

思维:

动态计划

Use two two-dimensional array g, h to save the current maximum and minimum results respectively Enumerate integers and operators;

state transition equation is: g(i,j)=max(g(i,j),g(i-1,j-1)f(j)a(i) ,h(i-1,j-1)f(j)a(i))

                             h(i,j)=max(h(i,j),h(i-1,j-1)f(j)a(i),g(i-1,j-1)f(j)a(i))

The initial condition is g(0,0)=h(0,0)=k The answer is g(n,m)

#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
#define INF 10000000000000000
Using namespace std;
Int n,m;
LL k,a[1005]={0};
LL g[1005][10],h[1005][10];
String s;
Void Init()
{
Scanf("%d%d%lld",&n,&m,&k);
For(int i=1;i<=n;i++)scanf("%lld",&a[i]);
Cin>>s;
s=" "+s;
}
LL Cal(LL a,char c,LL b)
{
If(c=='+')return a+b;
If(c=='-')return a-b;
If(c=='*')return a*b;
If(c=='/')return a/b;
}
LL Max(LL a,LL b)
{
If(a>b)return a;
Return b;
}
LL Min(LL a,LL b)
{
If(a<b)return a;
Return b;
}
Void Solve()
{
/ / Initialize
//memset(g,0,sizeof(g));
//memset(h,0,sizeof(h));
For(int i=0;i<=n;i++)
For(int j=0;j<s.length();j++)
{
g[i][j]=-INF;
h[i][j]=INF;
}
g[0][0]=h[0][0]=k;

//Action rules
Int Len=s.length()-1;
For(int i=1;i<=n;i++)
For(int j=0;j<=Len;j++)
{
g[i][j]=-INF;
h[i][j]=INF;
If(j>i)continue;
If(i>j)g[i][j]=g[i-1][j];
If(j>0)
{
g[i][j]=Max(g[i][j], Cal(g[i-1][j-1], s[j], a[i])));
g[i][j]=Max(g[i][j], Cal(h[i-1][j-1], s[j], a[i])));
}

h[i][j]=h[i-1][j];
If(j>0)
{
h[i][j]=Min(h[i][j], Cal(h[i-1][j-1], s[j], a[i])));
h[i][j]=Min(h[i][j], Cal(g[i-1][j-1], s[j], a[i])));
}
//printf("%d**%d**%lld**%lld\n",i,j,g[i][j],h[i][j]);
}

Printf("%lld\n",g[n][Len]);
}
Int main()
{
Int T;
Scanf("%d",&T);
While(T--)
{
Init();
Solve();
}
Return 0;
}
/*
1
5 4 833
712 -543 347 -135 -33
-/*+
*/

Note: 1. Up to five operators, the absolute value of each number is up to 1000, should be infinitely large for 10^15 ++

2. The array is bigger, not against the upper limit Open

3. Note that the legal status cannot be transferred from the redundant illegal status

D.Sequence (not exceeded)

题意: Set the length to M, the maximum number of each position is N The maximum number of occurrences of each number in the string is x, and the expectation of x is

.F.Modular Production Line (not exceeded)

题意: Give a certain number of intervals, each interval has a Weight, seeking the maximum number of total sums in the case where the number of coverages does not exceed k:

思维:费流