Warning: session_start(): open(/tmp/sess_9fe7fa483d5186e074307ad88cc50597, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== CF Edu Round 94 ======
===== D =====
**题意：**给定一个序列最大长度为3e3，问有多少个四元组$(i,j,k,l)$满足$i
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int read()
{
int x = 0, flag = 1;
char c = getchar();
while ((c > '9' || c < '0') && c != '-')
c = getchar();
if (c == '-')
flag = 0, c = getchar();
while (c <= '9' && c >= '0')
{
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return flag ? x : -x;
}
const int MAX = 3e3 + 10;
int pic[MAX];
pair seg[MAX * MAX];
int tot;
ll dp[MAX][MAX];
inline void init(int n)
{
tot = 0;
for (int i = 0; i <= n;i++)
memset(dp[i], 0, sizeof(ll) * (n + 1));
}
int main()
{
int t = read();
while(t--)
{
int n = read();
ll ans = 0;
for (int i = 1; i <= n;i++)
pic[i] = read();
for (int i = 1; i
===== E =====
**题意：**积木大赛变种，新增操作，把一堆积木去掉任意个。数据范围5e3
**题解：**开始想成dp写到后面发现完全不是dp就是一个贪心，对于一个区间的积木，要么一个个的全都去掉，要么让最小值直接去掉，然后递归计算两边。由于要取区间最小值，所以我当时写了个线段树，后来发现完全不需要，这个不是个dp，整个复杂度不是$n^2$，因为每次贪心会使得区间长度减一，所以复杂度是$O(n)$的，所以即便是暴力取最小值，也不过是$n^2$的复杂度，完全可以过。（所以这题数据范围还可以加强）
#include
#include
#include
#include
#include
#include
#define ls (node << 1)
#define rs ((node << 1) | 1)
using namespace std;
const int MAX = 5e3 + 20;
int read()
{
int x = 0, flag = 1;
char c = getchar();
while ((c > '9' || c < '0') && c != '-')
c = getchar();
if (c == '-')
flag = 0, c = getchar();
while (c <= '9' && c >= '0')
{
x = (x << 3) + (x << 1) + c - '0';
c = getchar();
}
return flag ? x : -x;
}
int mmin[MAX << 2];
int pic[MAX];
int dp[MAX][MAX],n;
inline int get_min(int x,int y)
{
if (pic[x] < pic[y])
return x;
else
return y;
}
void build(int node,int l,int r)
{
if (l == r)
{
mmin[node] = l;
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
mmin[node] = get_min(mmin[ls] , mmin[rs]);
}
inline int qurry(int node, int l, int r, int L, int R)
{
if (l == L and r == R)
return mmin[node];
else
{
int mid = (L + R) >> 1;
if (r <= mid)
return qurry(node << 1, l, r, L, mid);
else if (l >= mid + 1)
return qurry((node << 1) | 1, l, r, mid + 1, R);
else
return get_min(qurry(node << 1, l, mid, L, mid) , qurry((node << 1) | 1, mid + 1, r, mid + 1, R));
}
}
int mfs(int l,int r,int mins)
{
if (l>r)
return 0;
if (dp[l][r] != -1)
return dp[l][r];
if (l == r and pic[l] - mins <=0)
return 0;
int pos = qurry(1, l, r, 1, n);
int ann = min(r - l + 1, mfs(l, pos - 1, pic[pos]) + mfs(pos + 1, r, pic[pos]) + pic[pos]-mins);
dp[l][r] = ann;
return ann;
}
int main()
{
n = read();
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n;i++)
pic[i] = read();
build(1, 1, n);
cout << mfs(1, n,0);
}