Codeforces Round #FF (Div. 1)-A,B,C
A:DZY Loves Sequences
一開始看錯題了。。sad。
題目很簡單，做法也很簡單。DP一下就好了。
dp[i][0]:到當前位置，沒有任何數改變，得到的長度。
dp[i][1]:到當前位置，改變了一個數，得到的長度
不過需要正向求一遍，然後反向求一遍。
#include
#include
#include
#include
#include
using namespace std;
#define maxn 110000
int dp[maxn][3];
int num[maxn];
int a[maxn];
int n;
void dos(int maxx)
{
memset(dp,0,sizeof(dp));
memset(num,-1,sizeof(num));
for(int i=n; i>=1; i--)
{
if(a[i]=a[i+1])
{
if(dp[i][1]a[i-1])
{
dp[i][0]=dp[i-1][0]+1;
}
else
{
dp[i][0]=1;
}
dp[i][1]=dp[i][0];
num[i]=a[i];
if(a[i]>num[i-1])
{
if(dp[i][1]B：DZY Loves Modification
我們可以發現選擇一個橫行，豎行的大小順序不變，只是每一個豎行都下降了p。
所以我們可以枚舉選擇了x個橫行，y個豎行。
#include
#include
#include
#include
#include
#include
using namespace std;
#define maxn 1100
#define LL __int64
int mp[maxn][maxn];
int hh[maxn];
int ll[maxn];
LL ph[1100000];
LL pl[1100000];
priority_queueque;
int n,m,k,p;
void chu()
{
ph[0]=pl[0]=0;
while(!que.empty())que.pop();
for(int i=1;i<=n;i++)
{
que.push(hh[i]);
}
for(int i=1;i<=k;i++)
{
int x=que.top();
que.pop();
ph[i]=ph[i-1]+(LL)x;
x=x-p*m;
que.push(x);
}
while(!que.empty())que.pop();
for(int i=1;i<=m;i++)
{
que.push(ll[i]);
}
for(int i=1;i<=k;i++)
{
int x=que.top();
que.pop();
pl[i]=pl[i-1]+(LL)x;
x=x-p*n;
que.push(x);
}
}
int main()
{
while(~scanf("%d%d%d%d",&n,&m,&k,&p))
{
memset(hh,0,sizeof(hh));
memset(ll,0,sizeof(ll));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&mp[i][j]);
hh[i]+=mp[i][j];
ll[j]+=mp[i][j];
}
}
chu();
LL ans=pl[k];
for(int i=1;i<=k;i++)
{
LL x=(LL)i*(LL)(k-i);
x=(LL)x*(LL)p;
ans=max(ans,pl[k-i]+ph[i]-x);
}
cout
主要是兩個性質：
1,兩個斐波那契數列相加依然是一個斐波那契數列。
2，根據斐波那契數列的前兩項可以O（1）的時間內得出任意一個位置的斐波那契數，和任意長度的斐波那契數列的合。
剩下的東西就是簡單的區間求和問題了。
#include
#include
#include
#include
#include
#include
#include
#include
