题意
输入n和k，表示输入n个整数和可以擦除的次数k，如果至多擦除k次能是的数组中的序列是不上升或者是不下降序列，就是魔力数组，否则不是。
解题思路
分别求最长不下降和不上升子序列的长度，看不符合要求的数字和k的大小。
这里使用优化后的求解最长不上升和不下降子序列的算法。
#include <cstdio>
#include <algorithm>
using namespace std; const int maxn = ;
const int inf = ;
int A[maxn], B[maxn], g[maxn], d[maxn];
int n, t; int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &t);
for(int i = ; i < n; i++) {
scanf("%d", &A[i]);
} for(int i = ; i <= n; i++) {
g[i] = inf;
}
for(int i = ; i < n; i++) {
int k = upper_bound(g + , g + n + , A[i]) - g;
d[i] = k;
g[k] = A[i];
}
int s1 = ;
for(int i = ; i < n; i++)
if(s1 < d[i])
s1 = d[i]; int j = ;
for(int i = n - ; i >= ; i--) {
B[j++] = A[i];
}
for(int i = ; i <= n; i++) {
g[i] = inf;
}
for(int i = ; i < n; i++) {
int k = upper_bound(g + , g + n + , B[i]) - g;
d[i] = k;
g[k] = B[i];
}
int s2 = ;
for(int i = ; i < n; i++)
if(s2 < d[i])
s2 = d[i]; //printf("%d %d\n",s1,s2);
int ans = max(s1, s2);//最长上升或者下降子序列，取大值意味者修改更少
if(n - t <= ans)
printf("A is a magic array.\n");
else
printf("A is not a magic array.\n");
}
return ;
}
题意
给出n个屏幕和k个光源，要求的是从n个屏幕中任意的k个屏幕显示不同颜色的光源至少需要几根电缆
解题思路
有两个出发点
从屏幕出发，前k个屏幕都单独和k个光源连接，剩下n-k个屏幕应该和每个光源都有连接，否则随意挑的时候，可能会出现重复。故总的电缆数是k+(n-k)*k。
从光源出发，每个光源至少应该和（n-k+1）个屏幕相连，这样选出的k个屏幕才能可以组成k种不同的光源点。故总的电缆数是（n-k+1）* k。
#include <cstdio> int main()
{
long long n, k;
while(scanf("%lld%lld", &n, &k) != EOF) {
printf("%lld\n", k *( n - k + ));
}
return ;
}
题意
首先定义了斐波那契数列F0 = 0，F1 = 1;
Fn = Fn - 1 + Fn - 2（n>=2）.
给出一个k，如果一个正整数能够由连续（可重复）的斐波那契数加和得到，就是一个好数，否则就是一个坏数。现在给出一个k，问最小的坏数是多少。
解题思路
首先应该想到的应该是当k = 1 时，最小的坏数是5 - 1 = 4；
当k = 2 时，最小的坏数是13 - 1 = 12；
当k = 3 时，最小的坏数是34 - 1 = 33；
然后如果拿5为斐波那契数的第一项，8位第二项，可以发现规律就是对于输入的k，答案是第f(2*k+1)项斐波那契数 - 1。
不过题中给出的k的范围是（1<=k<=10^9），最大可能是第2*10^9项斐波那契数。就需要矩阵快速幂计算某一项斐波那契数了。代码如下：
#include <cstdio>
#include <cstring>
typedef long long ll;
const int mod = ;
struct Matrix {
ll x[][];
};
Matrix Mmul(Matrix a, Matrix b) {
Matrix tmp;
memset(tmp.x, , sizeof(tmp.x));
for(int i = ; i < ; i++) {
for(int j = ; j < ; j++) {
for(int k = ; k < ; k++) {
tmp.x[i][j] = (tmp.x[i][j] + a.x[i][k] * b.x[k][j] % mod) % mod;
}
}
}
return tmp;
}
Matrix Mqpow(Matrix a, ll n) {
Matrix tmp;
for(int i = ; i < ; i++) {
for(int j = ; j < ; j++) {
tmp.x[i][j] = i == j ? : ;
}
} while(n) {
if(n&)
tmp = Mmul(tmp, a);
a = Mmul(a, a);
n >>= ;
}
return tmp;
}
int main()
{
ll k;
while(scanf("%lld", &k) != EOF) {
Matrix st;
st.x[][] = ; st.x[][] = ;
st.x[][] = ; st.x[][] = ; Matrix init;
init.x[][] = ; init.x[][] = ;
init.x[][] = ; init.x[][] = ; st = Mqpow(st, * k + );
st = Mmul(st, init);
/*for(int i = 0; i < 2; i++) {
for(int j = 0; j < 2; j++) {
printf("%lld ", st.x[i][j]);
}
puts("");
}*/
printf("%lld\n", (st.x[][] - + mod) % mod);
}
return ;
}
HDU 6201 transaction transaction transaction
题意
给出由n-1条边联通的n个顶点的图（可以将其方便的看为一棵树），每个顶点都有卖一本书的价格，但是每个地方都不同，一个商人想从中赚取差价，但是点与点之间还有路费，问这个人最多能赚取多少钱？
解题思路
先将其转换为一棵树来处理，定义两种状态分别是：dp[u][0] 表示从u及其子孙结点中的一点买书（包括所花的路费）的最小值（由于是负数，所以也即求最大值）
dp[u][1]表示从u及其子孙结点中的一点卖书（包括所花的路费）的最大值
那么从u结点及其子孙结点买再卖给u及其子孙结点的利润，也就是一个结点的利润是dp[u][0] +dp[u][1]。最后的答案就是取所有结点的最大值即可。代码如下：
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = + ; struct Node {
int v, w;
Node(int _v, int _w):v(_v),w(_w){};
}; vector<Node> vec[maxn];
int val[maxn];
int n, ans;
int dp[maxn][]; void dfs(int u, int pre) {
dp[u][] = -val[u];//从u结点及其子孙结点中的一点买书所花的最少的钱（一定是一个负数）
dp[u][] = val[u]; //从u结点及其子孙结点中的一点卖书所赚的最多的钱
for(int i = ; i < vec[u].size(); i++) {
int v = vec[u][i].v;
int w = vec[u][i].w;
if(v == pre) continue;
dfs(v, u);
//当前结点（买书）和它的子结点（买书）“加上”路费的值 谁更大（都是负数）
dp[u][] = max(dp[u][], dp[v][] - w);
//当前结点（卖书）和它的子结点（卖书）减去路费的值 谁更大
dp[u][] = max(dp[u][], dp[v][] - w);
}
ans = max(ans, dp[u][] + dp[u][]);
} int main()
{
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = ; i <= n; i++) {
scanf("%d", &val[i]);
vec[i].clear();
}
for(int i = ; i <= n - ; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
vec[u].push_back(Node(v, w));
vec[v].push_back(Node(u, w));
}
ans = ;
dfs(, -);
printf("%d\n", ans);
}
return ;
}
题意
给出n摞牌，排成一行，然后n个数表示每摞有多少张牌，还给出每一摞牌的罚值，我们可以通过将第一摞移动到最后来改变次数，使得拿更多的牌，拿取一摞的规则是一张一张的拿到手中并且使他们面朝上，拿完之后翻转一定数目的牌使之朝下，如果能够翻转的牌数等于该摞牌的罚值，表示可以继续往后拿，直至拿完。问最少移动几次使得拿取最多的牌。
解题思路
问循环移动的次数，我们先将其复制一遍到它的后面，然后通过最大子段和的思想，每次选取满足条件的最大子段，不同的是限制的条件是a[i]-b[i]的差要大于等于0，而结果是所有牌的数目，所以需要分开计算。代码如下：
#include <cstdio>
const int inf = ;
const int maxn = + ;
int a[maxn], b[maxn]; int main()
{
int n;
while(scanf("%d", &n) != EOF) {
for(int i = ; i <= n; i++) {
scanf("%d", &a[i]);
a[i + n] = a[i];
}
int x;
for(int i = ; i <= n; i++) {
scanf("%d", &x);
b[i] = a[i] - x;
b[i + n] = b[i];
} int sum1 = , sum2 = ;
int ans = ;
int l = , r = , tmp = ;
for(int i = ; i <= * n; i++) {
sum1 += a[i];
sum2 += b[i];
if(sum1 > ans) {
ans = sum1;
l = tmp;
r = i;
}
if(sum2 < ) {
sum1 = ;
sum2 = ;
tmp = i + ;
if(tmp > n + )
break;
}
}
printf("%d\n", l-);
}
return ;
}