Educational Codeforces Round 126 (Rated for Div. 2)
很容易想到dp
dp[i,0]表示前i个 第i个不换 的最小值
dp[i,1]表示前i个 第i个换 的最小值
转移一下就行了
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=30;
int n,T;
ll a[maxn],b[maxn],dp[maxn][2];
int main(){
cin>>T;
while(T--){
cin>>n;
memset(dp,0x7f,sizeof(dp));
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
dp[1][0]=dp[1][1]=0;
for(int i=2;i<=n;i++){
dp[i][0]=min(dp[i][0],abs(a[i]-a[i-1])+abs(b[i]-b[i-1])+dp[i-1][0]);
dp[i][0]=min(dp[i][0],abs(a[i]-b[i-1])+abs(b[i]-a[i-1])+dp[i-1][1]);
dp[i][1]=min(dp[i][1],abs(a[i]-a[i-1])+abs(b[i]-b[i-1])+dp[i-1][1]);
dp[i][1]=min(dp[i][1],abs(a[i]-b[i-1])+abs(b[i]-a[i-1])+dp[i-1][0]);
}
cout< 
首先操作数肯定是不会超过15的 因为最多乘2的15次就是32768的倍数了
再考虑加的操作 要进行加操作的话 一定是先进行加 再进行乘
比如先加1再乘2 和先乘2再加1加1 都能到4 但是先加一定是更好的
所以枚举就好了
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
int T;
int main(){
cin>>T;
while(T--){
int x,ans=1e9;cin>>x;
for(int i=0;i<=15;i++){
int now=x+i;
for(int j=0;j<=15;j++){
if(now%32768==0)
ans=min(ans,i+j);
now<<=1;
}
}
cout< 
这个题目开始我想的是最大高度一定是数列中最高的那个 但其实不然
比如 1 1 1 变为2 2 2需要5 但是变为 3 3 3 只需要4（这是这个题目的关键）
所以最后的高度还可能是maxx+1 但是一定不能再高了 再高的话一定会额外付出
注意long long
剩下的是乱搞一下就好
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define int ll
const int maxn=3e5+5;
int T;
int a[maxn];
signed main(){
cin>>T;
while(T--){
int n,x,maxx=0,ans=1e18;
cin>>n;
int cc=0;
for(int i=1;i<=n;i++)scanf("%d",&a[i]),maxx=max(maxx,a[i]);
while(cc<=1){
maxx+=cc;
int cnt1=0,cnt2=0;
for(int i=1;i<=n;i++)
cnt1+=(maxx-a[i])%2,cnt2+=(maxx-a[i])/2;
if(cnt1==cnt2)
ans=min(ans,cnt1+cnt2);
else if(cnt1>cnt2)
ans=min(ans,cnt2*2+(cnt1-cnt2)*2-1);
else if(cnt2>cnt1){
int lis=(cnt2-cnt1)*2/3;
int mod=(cnt2-cnt1)*2%3;
int jia;
if(mod==0)jia=0;
if(mod==1)jia=1;
if(mod==2)jia=2;
ans=min(ans,lis*2+cnt1*2+jia);
}
cc++;
}
cout< 
贪心 考虑倒叙操作 依次满足最后一个 这样一定最优
剩下就是统计答案了 因为这个是递减的序列 所以我们只需要知道此时有多少个序列 用上个位置减的数减去此时序列个数
就是这个位置应该减的 问题就是有些序列结束了怎么办？ 就在其开头位置标记一下就好了！！！这个操作是最重要的
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=3e5+5;
ll n,k,ans;
ll a[maxn],edd[maxn];
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
ll cnt=0,sum=0;
for(ll i=n;i>=1;i--){
sum-=cnt;
a[i]-=sum;
cnt-=edd[i];
if(a[i]<=0)continue;
ll res=min(k,i);
ll need=a[i]/res;
if(a[i]%res)need++;
ans+=need;
cnt+=need;
sum+=need*res;
if(i-res>=0)
edd[i-res]+=need;
}
cout<