MMT2. 队列得分
描述
小M和大M要通过选择元素组成队列进行得分pk。目前存在队列S1,S2,S3...Sn,每个元素包括2个正整数属性set和value.从中选出任意K个元素S[i1],S[i2]...S[ik],保证顺序不变即i1 < i2 < i3< ... < ik,组成新的队列P1,P2,P3......Pk.我们通过一个机制评价队列的好坏:
Base=P1.value+P2.value+...Pk.value,
Bonus=10*t;t为新队列中Pi.set=P(i+1).set的i个数.
最终得分Score=Base-Bonus;求Score的最大值和取最大值时新队列元素个数的最小值.
输入描述
第一行包含一个数N(0 < N <= 500)输出描述
Score的最大值和新队列元素个数的最小值示例1
输入:
5 1 10 1 5 2 4 3 9 4 8
输出:
31 4
说明:
选S1,S3,S4,S5C 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-08-29
#include<stdio.h>
int main()
{
int n,i,j,sum=0,num=0;
scanf("%d ",&n);
int a[2][n];
for(i=0;i<n;i++)
{
scanf("%d %d",&a[0][i],&a[1][i]);
}
for(i=0;i<n-1;i++)
{
if(a[0][i]!=a[0][i+1])
{
sum=sum+a[1][i];
num++;
}
else
{
if(a[1][i]>10&&a[1][i+1]>10)
{
sum=sum+a[1][i]-10;
num++;
}
else if(a[1][i]>10&&a[1][i+1]<=10)
{
a[1][i+1]=a[1][i];
}
else if(a[1][i]<=10&&a[1][i+1]<=10)
{
if(a[1][i]>a[1][i+1]) a[1][i+1]=a[1][i];
else;
}
else;
}
}
printf("%d %d\n",sum+a[1][n-1],num+1);
}
C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-10-31
#include <stdio.h>
#define MAX_N 505
int set[MAX_N], value[MAX_N], num[MAX_N], dp[MAX_N];
void solve(int n)
{
int i, j, ans = 0, ansNum = 0, cur, curNum;
for (i = 0; i < n; ++i)
{
cur = curNum = 0;
for (j = 0; j < i; ++j)
{
if (cur < dp[j] - (set[i] == set[j] ? 10 : 0))
{
cur = dp[j] - (set[i] == set[j] ? 10 : 0);
curNum = num[j];
}
}
dp[i] = cur + value[i];
num[i] = curNum + 1;
if (ans < dp[i])
{
ans = dp[i];
ansNum = num[i];
}
}
printf("%d %d\n", ans, ansNum);
}
int main()
{
int n, i;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%d%d", set + i, value + i);
}
solve(n);
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-05-20
#include <stdio.h>
#define MAX_N 505
int set[MAX_N], value[MAX_N], num[MAX_N], dp[MAX_N];
void solve(int n)
{
int i, j, ans = 0, ansNum = 0, cur, curNum;
for (i = 0; i < n; ++i)
{
cur = curNum = 0;
for (j = 0; j < i; ++j)
{
if (cur < dp[j] - (set[i] == set[j] ? 10 : 0))
{
cur = dp[j] - (set[i] == set[j] ? 10 : 0);
curNum = num[j];
}
}
dp[i] = cur + value[i];
num[i] = curNum + 1;
if (ans < dp[i])
{
ans = dp[i];
ansNum = num[i];
}
}
printf("%d %d\n", ans, ansNum);
}
int main()
{
int n, i;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%d%d", set + i, value + i);
}
solve(n);
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-04-21
#include <stdio.h>
#define MAX_N 505
int set[MAX_N], value[MAX_N], num[MAX_N], dp[MAX_N];
void solve(int n)
{
int i, j, ans = 0, ansNum = 0, cur, curNum;
for (i = 0; i < n; ++i)
{
cur = curNum = 0;
for (j = 0; j < i; ++j)
{
if (cur < dp[j] - (set[i] == set[j] ? 10 : 0))
{
cur = dp[j] - (set[i] == set[j] ? 10 : 0);
curNum = num[j];
}
}
dp[i] = cur + value[i];
num[i] = curNum + 1;
if (ans < dp[i])
{
ans = dp[i];
ansNum = num[i];
}
}
printf("%d %d\n", ans, ansNum);
}
int main()
{
int n, i;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%d%d", set + i, value + i);
}
solve(n);
return 0;
}
C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2020-11-01
#include <stdio.h>
#define MAX_N 505
int set[MAX_N], value[MAX_N], num[MAX_N], dp[MAX_N];
void solve(int n)
{
int i, j, ans = 0, ansNum = 0, cur, curNum;
for (i = 0; i < n; ++i)
{
cur = curNum = 0;
for (j = 0; j < i; ++j)
{
if (cur < dp[j] - (set[i] == set[j] ? 10 : 0))
{
cur = dp[j] - (set[i] == set[j] ? 10 : 0);
curNum = num[j];
}
}
dp[i] = cur + value[i];
num[i] = curNum + 1;
if (ans < dp[i])
{
ans = dp[i];
ansNum = num[i];
}
}
printf("%d %d\n", ans, ansNum);
}
int main()
{
int n, i;
scanf("%d", &n);
for (i = 0; i < n; ++i)
{
scanf("%d%d", set + i, value + i);
}
solve(n);
return 0;
}